题解 | #迷宫问题#

与其说分享解题思路，不如说是小白的吐苦水。

本题选择用 DFS 来做，先是思考了下构建 DFS 的结构：

• 目标是到达终点，同时记录路径，最后选择最短路径输出，所以需要记录路径的变量，记录最短路径的变量，记录路径长度和最短长度的变量。其他变量则看 dfs 实现的风格了而设置了。

• 设置 dfs 的出口，根据目标，出口1 就是到达终点，这时就需要来判断该路径是否最短； 出口 2 就是此路不通。

• 所以其他情况就代表在路上，假设位于 x,y 处，你有四个方向可以前进，但需要排除你来时的路，所以可以将走过的路做标记，比如设置其为-1或者其他数，表示走过。

上面情况讲清楚了，接下来就是实现了，dfs 的特点就是除了出口外对于每一点的处理都是相似的，所以需要总结处理特点，对于下一步的处理有两种方法，①是直接判断下一点是否可达，②是先进入下一点，再判断是否可达：：我用的第二种，不太聪明的亚子

• 假设位于 x,y 处，现在要先判断该点是否为终点，是否该点不通或已走过，如果是个可达点，记录该点到路径变量中，然后设置该点的值为 -1，表示来过，然后就是进入下一点，有四种可能，(x+1,y), (x-1,y), (x,y+1), (x,y-1), 这四个方向都有可能到达终点，所以对这四种可能进行 或 运算。
• 走完四种可能性要将假设中走过的路径恢复，即把设置为-1的点重新设置为 0

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int trace[100][2] = {0},        // 记录路径
    min_trace[100][2] = {0};          // 记录最短路径
int maze[10][10];              // 迷宫
// int curStep = 0;               // 表示当前前进的步数，也是最终的路径长度
int minStep = 100;               // 最短路径
int flag = 0;

int findTrace(int curXidx, int curYidx, int row, int col, int curStep);

int main() {
    int row, col;
    while (scanf("%d %d", &row, &col) != EOF) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                scanf("%d", &maze[i][j]);
            }
        }
        flag = findTrace(0, 0, row, col, 0);
        if (flag == -1) {
            printf("ERROR\n");
        } else {
            for (int i = 0; i <= minStep; i++) {
                printf("(%d,%d)\n", min_trace[i][0], min_trace[i][1]);
            }
        }
    }
    return 0;
}

int findTrace(int curXidx, int curYidx, int row, int col, int curStep) {
    
    int f = 0;
    // 到达终点
    if (curXidx == row - 1 && curYidx == col - 1) {
        trace[curStep][0] = curXidx;
        trace[curStep][1] = curYidx;
        if (curStep < minStep) {	// 复制最短路径
            minStep = curStep;
            for (int i = 0; i <= minStep; i++) {
                min_trace[i][0] = trace[i][0];
                min_trace[i][1] = trace[i][1];
            }
        }
        return 1;
    }
    // 该点可达
    if ((curXidx >= 0 && curXidx < row ) &&
            (curYidx >= 0 && curYidx < col) &&
            (maze[curXidx][curYidx] == 0)) {
        
        trace[curStep][0] = curXidx;
        trace[curStep][1] = curYidx;
        ++curStep;
        
        maze[curXidx][curYidx] = -1;    // 表示走过
      
        f = findTrace(curXidx + 1, curYidx, row, col, curStep) ||
            findTrace(curXidx, curYidx + 1, row, col, curStep) ||
            findTrace(curXidx, curYidx - 1, row, col, curStep) ||
            findTrace(curXidx - 1, curYidx, row, col, curStep);
      
        maze[curXidx][curYidx] = 0;    // 恢复
        
    } 
  	// 此路不通
    else {
        return 0;
    }
    return f;
}