[数据结构与算法]数据结构：迷宫问题（递归）

看代码咯，懒！

package com.cx;

public class MiGong {
    public static void main(String[] args) {
        //先创建一个二维数组，模拟迷宫
        //地图
        int array[][] = new int[8][7];
        //使用1表示墙

        //两处障碍墙
        array[3][1] = 1;
        array[3][2] = 1;

        //上下墙体设置
        for(int i = 0; i < array[1].length;i++){
            array[0][i]=1;
            array[7][i]=1;
        }
        //左右的墙
        for(int i = 0;i<array.length;i++){
            array[i][0]=1;
            array[i][6]=1;
        }
        System.out.println("地图的初始状态：");
        for(int i = 0; i <array.length;i++){
            for(int  j = 0 ; j < array[i].length;j++){
                System.out.print(array[i][j]+" ");
            }
            System.out.println();
        }
        //开始从起点(1,1)找到达终点(6,5)的路
        isRun2(array,1,1);
        System.out.println("寻找后的地图路线：");
        for(int i = 0; i <array.length;i++){
            for(int  j = 0 ; j < array[i].length;j++){
                System.out.print(array[i][j]+" ");
            }
            System.out.println();
        }

    }

    /**
     * 使用递归回溯来个小球找路
     * 1.小球的开始位置：1.1
     * 2.小球的终点位置：6.5  如果小球能找个这个位置，表示通路找到了
     * 3.  1:代表墙体，不能走  2：代表通路，可以走  3：代表这里已经走过了，并且这里走不通  0：初始状态，表示没走过且可以走该点
     * 4.策略是：下->右->上->左，如果该点走不通，则回溯
     */
    /**
     * @param array 表示地图
     * @param i     i，j表示从哪个位置开始找
     * @param j
     * @return  找到通路，就返回true，否则返回false
     */
    public static boolean isRun(int [][]array,int i, int j) {
        if (array[6][5] == 2) {//通路已经找到了
            return true;
        }else {
            if (array[i][j] == 0) {//此点还没有走过
                //表示可以走
                array[i][j] = 2;//假定该点是可以走通
                //下，右，上，左  走的优先级是下右上左
                if (isRun(array, i + 1, j)) { //向下走
                    return true;
                } else if (isRun(array, i, j + 1)) {//向右走
                    return true;
                } else if (isRun(array, i - 1, j)) {//向上走
                    return true;
                } else if (isRun(array, i, j - 1)) {//向左走
                    return true;
                } else {//下，右，上，左都走不通，表示该点是走不通的，死路
                    array[i][j] = 3;
                    return false;
                }
            } else {//array[i][j]!=0,可能为1,2,3   1：墙  2：走过了 3：死路
                return false;
            }
        }
    }
        //策略是上->右->下->左
    public static boolean isRun2(int [][]array,int i, int j) {
        if (array[6][5] == 2) {//通路已经找到了
            return true;
        }else {
            if (array[i][j] == 0) {//此点还没有走过
                //表示可以走
                array[i][j] = 2;//假定该点是可以走通
                //下，右，上，左  走的优先级是下右上左
                if (isRun2(array, i - 1, j)) { //向上走
                    return true;
                } else if (isRun2(array, i, j + 1)) {//向右走
                    return true;
                } else if (isRun2(array, i + 1, j)) {//向下走
                    return true;
                } else if (isRun2(array, i, j - 1)) {//向左走
                    return true;
                } else {//下，右，上，左都走不通，表示该点是走不通的，死路
                    array[i][j] = 3;
                    return false;
                }
            } else {//array[i][j]!=0,可能为1,2,3   1：墙  2：走过了 3：死路
                return false;
            }
        }
    }
}