算法-迷宫问题-回溯

package datastructure.migong;




public class Test {
    public static void main(String[] args) {
        int[][] map = new int[8][8];
        for(int i = 0; i < 8; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }

        for(int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][7] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        map[3][3] = 1;

        setWay(map, 1, 1);

        for(int[] i : map) {
            for(int j : i) {
                System.out.print(j+"\t");
            }
            System.out.println();
        }
    }

    /**
     * 判断当前点能否走到终点
     * @param map 地图
     * @param i   当前的行
     * @param j   当前的列
     * @return   返回true表示该点走得通  走路规则右->下->左->上
     *
     * 该点是1表示是墙 2 表示该点走得通  3 表示该点走不通 0表示没有走   该地图开始默认没走的地方是0
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if(map[6][6] == 2) {//表示(6,6)已经走过,说明到达终点
            return true;
        }
        //判断该点的情况可能是0 1 2 3
        //如果是0，表示该点没有走
        if(map[i][j] == 0) {
            //先假设该点走得通(即从这点走可以到(6,6)这个点)，走不通再回溯，令该点为2
            map[i][j] = 2;//我要将最后的路线在地图上以2来表示
            //如果该点可以走通，然后判断下一点是否能走通
            //右能走通
            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 if (setWay(map, i - 1, j)) {//上可以走通
                return true;
            }else {//都走不通
                map[i][j] = 3;//这里就是回溯把刚刚假设的map[i][j]=2否定
                return false;
            }

        }else {//map[i][j]可以为1 3 这里不可能为2 因为2只有在map[i][j]==0才会出现
            return false;
        }
    }





}