题解 | #迷宫问题#
迷宫问题
http://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
#include<stdio.h>
// 思想：逐一遍历所有可能的可行路径，若当前可行路径距离小于小于最小的路径长度，则替换
// 定义结构体
typedef struct loca{
int x;
int y;
}LOCA;
// 设置全局变量-这些变量可在每个递推中都可被更新
int n_row,n_colum;
int maze[10][10];
int dist_min; //记录最短路径长度
LOCA loca[100],loca_min[100];//记录当前路径和最短路径
void search_path(int x,int y,int len);
int main(){
dist_min = 101;
int dist = 0;
scanf("%d %d",&n_row,&n_colum);
for(int i=0;i<n_row;i++){
for(int j=0;j<n_colum;j++){
scanf("%d",&maze[i][j]);
}
}
search_path(0,0,dist);
for(int i=0;i<dist_min;i++){
printf("(%d,%d)\n",loca_min[i].x,loca_min[i].y);
}
}
void search_path(int x,int y,int dist){
// 更新距离和保存当前位置
loca[dist].x = x;
loca[dist].y = y;
dist = dist + 1;
// 判断是否到达终点
if(x==n_row-1 && y==n_colum-1){
if(dist<dist_min){ // 若更短则更新
dist_min = dist;
for(int i=0;i<dist_min;i++){
loca_min[i].x = loca[i].x;
loca_min[i].y = loca[i].y;
}
}
}
else{
// 该四条语句即当前节点的四个可能的子节点，他们前面有相同的路径（相同的dist），但在此出现了分叉
maze[x][y] = -1; //******* 当前节点已经走过，之后不能在走到此位置，防止绕圈卡死******
if(maze[x][y+1]==0 && y+1<n_colum){ // yo
search_path(x,y+1,dist);
}
if(maze[x][y-1]==0 && y-1>=0){ //下
search_path(x,y-1,dist);
}
if(maze[x+1][y]==0 && x+1<n_row){ // 右
search_path(x+1,y,dist);
}
if(maze[x-1][y]==0 && x-1>=0){ // 左
search_path(x-1,y,dist);
}
maze[x][y] = 0; //***** 恢复（运行到此时，以此为出发点的所有路径都已经遍历完毕*******
}
}
