递归解决迷宫问题---java

目录

递归思路：

gitee地址

项目代码：

生成墙：

找路：setWay(int[][] map,int i,int j)

查看结果

输出结果：

总体代码如下：

递归思路：

1.递归必须要明确什么条件调用，什么条件结束。

2.递归必须向递归结束的方向逼近，否则就是死循环了。

3.遵循谁调用就将结果返回给谁。

---

gitee地址

maze文件

---

项目代码：

生成墙：

注解:墙如下所示

          1 1 1 1 1 1
          1 0 0 0 0 1
          1 0 0 0 0 1
          1 1 1 0 0 1
          1 0 0 0 0 1
          1 0 0 0 0 1
          1 1 1 1 1 1

---

int[][] map = new int[7][6];
        
        for (int i = 0;i 

找路：setWay(int[][] map,int i,int j) 
注解:map 地图  i 起点横坐标  j 起点纵坐标 1是墙，0是未走过，2是通的，3是不通
 
递归可以把问题看为很小的一个子问题，如果该子问题解决了，其他问题就都解决了
先判断结束的地方是第9到11行，其他就是重复调用自己。
先在起点处开始找路，如果该点是0则意味着没有走过，将该点假设为2，是可以通的路，就开始找路。先向下找，通就返回true，否则就返回；也是用setWap来找路的
                再向右找，通就返回true，否则就返回false表示不通；
 
                再向左找，通就返回true，否则就返回false表示不通；
 
                再向上找，通就返回true，否则就返回false表示不通；
 
                都不通就将该点设为3，返回false。
 
       4.如果不是0就是1,2,3；为1,3表示不通直接返回false；为2表示该点已经向下右左上走过了，但是没通，所以不是0就都返回false。
 
    public static boolean setWay(int[][] map,int i,int j){
        if(map[5][4] == 2){
            return true;
        }
        if(map[i][j] == 0){
            map[i][j] = 2;//将该点假设为通的，则先向下走，通则返回true，不通就向右走，
                         // 不通再向左走，不通就向上走，再不通就将改点设置为3并返回false
            if(setWay(map,i+1,j)){
                return true;
            }else if(setWay(map,i,j+1)){
                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;
                return false;
            }
        }else { //1,2,3的情况中，1是墙，3是不通就返回false，
                // 但是2的情况是，该路走过了，又走回来了，说明改点也是不通的
            return false;
        }


    }
 

查看结果 
注：setWay()是找路方法
 
		setWay(map,1,1);

        for (int i = 0;i 

输出结果： 
1 1 1 1 1 1 
1 2 0 0 0 1 
1 2 2 2 0 1 
1 1 1 2 0 1 
1 0 0 2 0 1 
1 0 0 2 2 1 
1 1 1 1 1 1 
 
总体代码如下： 
package DataStructures.Stack;


public class maze {
    public static void main(String[] args){

        int[][] map = new int[7][6];
        
        for (int i = 0;i