递归解迷宫问题

• 递归程序需要向退出条件逼近，否则就会形成死递归
• 递归在方法结束或者遇到return时返回给调用者

使用递归解迷宫问题，使用二维数组表示迷宫

• 0代表没有走过的路
• 1代表墙
• 2代表走过的路
• 3 代表走过的路，但是是死路
• *代表启始位置
• ^ 代表终点

假设有的迷宫地图如下：

1 1 1 1 1 1 1 1 1 
1 * 0 0 0 0 0 0 1 
1 1 1 1 0 0 0 0 1 
1 0 0 1 0 1 0 0 1 
1 0 0 1 0 1 0 0 1 
1 0 0 1 0 1 0 ^ 1 
1 1 1 1 1 1 1 1 1 

算法步骤：

1. 退出条件，走到终点maze[5][7]，即maze[5][7]=2
2. 回溯走法顺序为down 、right、up、left
3. 如果路没有走过（maze[i][j]=0）,首先将其标记为走过（maze[i][j]=2）,然后按照步骤2中的走法尝试继续往下走，如果发现不能往下走（上下左右都没有未走过的路了），则将这个路标记为死路maze[i][j]=3

package com.yz.ds;

/**
 *     0  代表没有走过的路
 *     1  代表墙
 *     2  代表走过的路
 *     3  代表走过的路，但是是死路
 *     *  代表启始位置
 *     ^  代表终点
 *
 *     1 1 1 1 1 1 1 1 1
 *     1 *             1
 *     1 1 1 1         1
 *     1     1   1     1
 *     1     1   1     1
 *     1     1   1   ^ 1
 *     1 1 1 1 1 1 1 1 1
 */
public class Maze {
    private static void printMazeStatus(int maze[][]) {
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[i].length; j++) {
                System.out.print(maze[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static boolean doWalkDown(int maze[][], int i, int j) {
        return doWalk(maze, i + 1, j);
    }

    private static boolean doWalkRight(int maze[][], int i, int j) {
        return doWalk(maze, i, j + 1);
    }

    private static boolean doWalkUp(int maze[][], int i, int j) {
        return doWalk(maze, i - 1, j);
    }

    private static boolean doWalkLeft(int maze[][], int i, int j) {
        return doWalk(maze, i, j - 1);
    }


    private static boolean doWalk(int maze[][], int i, int j) {
        if (maze[5][7] == 2) {
            return true;
        } else if (maze[i][j] == 0) {
            maze[i][j] = 2;
            if (doWalkDown(maze, i, j) ||
                    doWalkRight(maze, i, j) ||
                    doWalkUp(maze, i, j) ||
                    doWalkLeft(maze, i, j)) {
                return true;
            } else {
                maze[i][j] = 3;
                return false;
            }
        } else {
            return false;
        }

    }


    public static void main(String[] args) {

        int maze[][] = new int[7][9];
        for (int i = 0; i < 9; i++) {
            maze[0][i] = maze[6][i] = 1;
        }
        for (int i = 0; i < 7; i++) {
            maze[i][0] = maze[i][8] = 1;
        }
        maze[2][1] = maze[2][2] = maze[2][3] = 1;
        maze[3][3] = maze[4][3] = maze[5][3] = 1;
        maze[3][5] = maze[4][5] = maze[5][5] = 1;
        
        
        doWalk(maze, 1, 1);
        printMazeStatus(maze);

    }
}

最终输出如下:

1 1 1 1 1 1 1 1 1 
1 2 2 2 2 0 0 0 1 
1 1 1 1 2 2 2 0 1 
1 0 0 1 3 1 2 0 1 
1 0 0 1 3 1 2 0 1 
1 0 0 1 3 1 2 2 1 
1 1 1 1 1 1 1 1 1