递归回溯之迷宫问题详解

递归回溯之迷宫问题详解

说明

1. 迷宫问题：即设置一个入口，然后按照指定的策略寻找出口
2. 使用二维数组模拟迷宫，设定 0 为可以走的点 ，设定 1 为迷宫的墙体，即不能走，设定 2 为可以走并且已经走过的点，设定 3 为走过但不能走通
3. 然后设定不同的策略，可以设定先下再右再上再左，也可以设定其他策略，每一种策略都对应不同的走法
4. 核心思路为找路的方法，如果找到路，则返回true，如果没找到路，则返回false
5. 如果按照指定策略上下左右都走完还没有找到路，则回溯
6. 详解见源码

源码及详解

package algorithm.recursion;

/**
 * @author AIMX_INFO
 * @version 1.0
 */
public class MiGong {
    public static void main(String[] args) {
        //定义迷宫的大小，即长和宽
        int row = 8;
        int col = 7;
        //定义二维数组模拟迷宫
        int[][] map = new int[row][col];
        //设定 1 代表迷宫的墙
        //先将第一行和最后一行置为1
        for (int i = 0; i < col; i++) {
            map[0][i] = 1;
            map[row - 1][i] = 1;
        }
        //再将第一列和最后一列置为1
        for (int i = 0; i < row; i++) {
            map[i][0] = 1;
            map[i][col - 1] = 1;
        }
        //再将第四行第二列和第三列置为1
        map[3][1] = 1;
        map[3][2] = 1;
        //从(1, 1)开始走，走到 (6, 5)的路径
        setWay(map, 1, 1);
        //查看迷宫的状态
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "\t\t");
            }
            System.out.println();
            System.out.println();
        }
    }

    //编写找路的方法
    //假定 0 代表还没有走过的路 1 代表墙 2 代表可以走的路 3代表已经走过但走不通，即死路
    //指定找路的策略，先向下找，如果走不通则向右 如果右走不通 则向上 如果还走不通 则向左
    //设置起始点为[1, 1] 设置终点，即迷宫的出口为[7, 6]
    /**
     * @param map 二维数组，即迷宫
     * @param i   当前位置的水平距离
     * @param j   当前位置的垂直距离
     * @return    返回是否找到路
     */
    public static boolean setWay(int[][] map, int i, int j) {
        //如果找到迷宫出口，则返回true
        if (map[6][5] == 2) {
            return true;
            //否则就继续找
        } else {
            //假定当前位置是0，即可以走
            if (map[i][j] == 0) {
                //则按照给定的策略找路 下-->右-->上-->左
                //如果当前位置可以走，先设置标志，即将当前位置设为2
                map[i][j] = 2;
                //先向下找路，如果找到，返回true
                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 {
                    //如果上下左右都走不通，则说明是一条死路，直接置为3
                    map[i][j] = 3;
                    return false;
                }
            } else {
                //否则当前位置可能是1 ， 2， 3 ，则都不能走，返回false
                return false;
            }
        }
    }
}

递归回溯之迷宫问题详解

原文：https://www.cnblogs.com/mx-info/p/14825893.html