java解决迷宫问题

问题描述：创建一个迷宫，给出起始位置和终点位置，找出一条通路

思路分析：1.迷宫可以用一个二维数组去定义

2.把出口的坐标设为回溯的出口

3.定义策略，例如：先向下走，再向右走，再向上走，最后向左走

代码部分：

//在迷宫中，我们把墙或障碍物设为1
public class Migong {
    public static void main(String[] args) {
        int map[][] =  new int[8][7]; //创建一个8*7的地图
        //把第一行和最后一行的值设为1
        for(int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //把第一列和最后一列的值设为1
        for(int j = 0; j < 8; j++) {
            map[j][0] = 1;
            map[j][6] = 1;
        }
       
        //在地图内设置障碍物，可自行设置
        map[3][1] = 1;
        map[3][2] = 1;
       
        //创建一个对象t1
        T t1 = new T();
       
        //设置一个初始位置的坐标
        t1.miGong(map,1,1);
        
        //输出一条通路
        for(int i = 0; i < 8; i++) {
            for(int j= 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
}

//创建一个类 T
class T {
    //在这个方法中，0表示可走的路，1表示障碍物，2表示已走过的路，3表示一个死路
    public boolean miGong(int map[][],int i,int j) {
        //map[6][5] == 2表示出口
        if(map[6][5] == 2) {
            return true;
        } else {
            //当map[i][j] == 0时，表示可走，此时先令该路是通路，赋值为2
            if(map[i][j] == 0) {
                map[i][j] = 2;
                //设置一个策略
                //先向下走，再向右走，再向上走，最后向左走
                if(miGong(map,i + 1,j)) {
                    return true;
                } else if(miGong(map,i,j + 1)) {
                    return true;
                } else if(miGong(map,i - 1, j)) {
                    return true;
                } else if(miGong(map,i,j - 1)) {
                    return true;
                } else {        //如果上下左右都走不通，赋值为3，表示这个路是死路
                    map[i][j] = 3;
                    return false;
                }
            } else {        //如果是1，2，3，则表示不能走
                return false;
            }
        }
    }
}