题解 | #迷宫问题#

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n, m;
//int map[100][100]={0};//存放地图,下面我用的动态数组；
int M[2][100] = {0};//存放最短路径
int buf[2][100] = {0};//暂存成功的路径
int v[100][100] = {0};//存放走过的节点，1表示走过，0表示为走过
int dx[] = {0, 1, 0, -1};//对应右下左上
int dy[] = {1, 0, -1, 0};
int min = 0xff;//最短路径步数，起点算第0步

void dfs(int** map, int x, int y, int step) {
    //记录当前路径
    buf[0][step] = x - 1;
    buf[1][step] = y - 1;
    v[x][y] = 1;//标记当前点已走过
    //找到出口
    if ((x == n) && (y == m)) {
        //记录最短路径
        if (step < min) {
            min = step;
            int i;
            for (i = 0; i <= step; i++) {
                M[0][i] = buf[0][i];
                M[1][i] = buf[1][i];
            }
        }
        //找到终点，回溯
        //v[x][y] = 0;//只需找到一条路径，所以不需要
        //buf[0][step] = 0;//buf可以不复位
        //buf[1][step] = 0;
        return;
    }
    int i;
    //未抵达终点，依次往右下左上进行bfs；
    for (i = 0; i < 4; i++) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        //下一节点未走过，且不为墙壁；
        if ((map[tx][ty] != 1) && (v[tx][ty] == 0)) {
            dfs(map, tx, ty, step + 1);
        }
    }
    //未到终点回溯
    //v[x][y] = 0; //只需找一条路径，走过的不需要再走
    //buf[0][step] = 0;
    //buf[1][step] = 0;
    return;
}



int main() {
    int i, j;
    scanf("%d %d", &n, &m);

    //创建动态数组，也可以直接用全局变量；
    int** map = (int**)malloc(sizeof(int*) * (n + 2));
    for (i = 0; i < (n + 2); i++) {
        map[i] = (int*)malloc(sizeof(int) * (m + 2));
    }
    //初始化MAP，补充边界为1；
    for (i = 0; i < (m + 2); i++) {
        map[0][i] = 1;
        map[n + 1][i] = 1;
    }
    for (j = 1; j < (n + 1); j++) {
        map[j][0] = 1;
        map[j][m + 1] = 1;
    }

    //从输入读取MAP;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    dfs(map, 1, 1, 0);

    for (i = 0; i <= min; i++) {
        printf("(%d,%d)\n", M[0][i], M[1][i]);
    }

    return 0;
}