题解 | #迷宫问题#

#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;  //***** 恢复（运行到此时，以此为出发点的所有路径都已经遍历完毕*******
    }
    
}