用递归解决迷宫问题

1.问题

图片描述:红色区域表示挡板,小球得到的路径与设置的找路策略有关

2.代码演示

package com.itguigu.recursion;

public class MiGong {
    public static void main(String[] args) {
        // 1.创建一个二维数组表示地图map
        int[][] map = new int[8][7];
        // 2.给地图添加挡板,1表示挡板
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
//        map[1][2] = 1;
//        map[2][2] = 1;
        // 3.展示地图
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        // 调用找路方法
        setWay(map, 1, 1);
        System.out.println("调用找路方法:");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
    // 使用递归来给小球找路

    /**
     * 思路分析:
     * 1.map表示地图
     * 2.i,j表示从哪个位置出发,(1,1)
     * 3.如果能找到(6,5),则说明通路找到
     * 4.约定:map[i][j]=0表示未走过;map[i][j]=1表示挡板;map[i][j]=2表示走过,是通路;map[i][j]=3表示走过,不通
     * 5.在走迷宫时要确定一个策略,我们采用:下 -> 右 -> 上 -> 左,如果走不通,再回溯
     *
     * @param map 表示地图
     * @param i
     * @param j
     * @return 找到通路返回true, 否则返回false
     */
    public static boolean setWay(int[][] map, int i, int j) {
        // 已经找到通路
        if (map[6][5] == 2) {
            return true;
        }
        if (map[i][j] == 0) { // 路未走过
            // 先假定路是通的
            map[i][j] = 2;
            if (setWay(map, i + 1, j)) { // 向下走
                return true;
            } else if (setWay(map, i, j + 1)) { // 向右走
                return true;
            } else if (setWay(map, i - 1, j)) { // 向上走
                return true;
            } else if (setWay(map, i, j - 1)) { // 向左走
                return true;
            } else {
                map[i][j] = 3;
                return false;
            }

        } else { // 路走过或是挡板,map[i][j]=1或2或3
            return false;
        }
    }
}