问题描述

约翰·米勒上尉接到上级命令，要去一个迷宫拯救被困其中的大兵瑞恩。迷宫由空地格子和障碍物——墙组成。现在米勒从(1,1)这个地方降落并进入迷宫，问找到瑞恩的最短路径。通过卫星定位到瑞恩所在坐标为(p, q)处,让你求解。

代码

/**
 * 约翰·米勒上尉接到上级命令，要去一个迷宫拯救被困其中的大兵瑞恩。
*迷宫由空地格子和不可穿透的墙组成。现在米勒从(1,1)这个地方降落并进入迷宫，问找到瑞恩的最短路径。
*通过卫星定位到瑞恩所在坐标为(p, q),让你求解。
 * @author XZP
 *
 */
public class SavingToRyan {
    // 给定一个迷宫，1表示墙，0表示空地
    public static int[][] maze = {
            {0, 0, 1, 0},
            {0, 0, 0, 0},
            {0, 0, 1, 0},
            {0, 1, 0, 0},
            {0, 0, 0, 1}
    };
    // 初始化一个控制方向的向量
    public static int[][] direction = {
            {0, 1}, // 左
            {1, 0}, // 下
            {0, -1}, // 右
            {-1, 0}  // 上
    };
    public static int[][] book = new int[5][4]; // 用于标记该格子是否走过
    // 迷宫的行列
    public static int row = 5;
    public static int col = 4;
    // 米勒出发的坐标x,y
    public static int startx = 1; 
    public static int starty = 1;
    // 瑞恩被困的位置p,q
    public static int p = 4;
    public static int q = 3;
    // 初始化一个全局变量保存最短路径
    public static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        book[0][0] = 1;
        dfs(1, 1, 0);
        System.out.println("救出瑞恩的最短路径为：" + min);
    }
    public static void dfs(int x, int y, int step) {
        int nx, ny;
        // 首先是当前的状态
        if (x == p && y == q) { // 找到瑞恩
            if (step < min) {
                min = step;
                System.out.println("x:" + x + " y:" + y + " p:" + p + " q:" + q + " step:" + step);
            }
            return;
        }
        System.out.println("x:" + x + " y:" + y);
        for (int k = 0; k < 4; k++) {
            nx = x + direction[k][0]; // 下一步的x,y值
            ny = y + direction[k][1];
            if (nx < 1 || nx > 5 || ny < 1 || ny > 4) {
                continue;
            }
            if (book[nx-1][ny - 1] == 0 && maze[nx - 1] [ny -1] == 0) { // 在迷宫内且没有障碍物，没有走过
                book[nx - 1][ny -1] = 1; // 这步很重要，如果没有就会栈溢出 ----------------------------     (1)
                dfs(nx, ny, step + 1);
                book[nx - 1][ny - 1] = 0; // 回退到这步要将其重新标记为能走的  ----------------------- （2）
            }
        }
    }
}

注意

作者因为一时疏忽，漏掉了注释（1）处对应的那行代码，于是测试的时候栈溢出，反复理了一下逻辑，都觉得没问题，再三跟踪调试之后，发现自己犯了一个低级错误：死递归。
如果不要注释（1）对应的代码，就会在下一步的格子中递归回来（这个应该比较好理解），如此往复！
那顺带说一下注释（2）对应的代码，就是尝试完（nx-1， ny - 1)对应的点之后需要将这个标记拿掉。有点绕，很多问题在这两步时最难理解！！！！故特别记录，以便加深自己的理解和运用。