迷宫问题 java（DFS，回溯法，递归）

2022 年 6 月 03 日
本文字数：1044 字
阅读完需：约 3 分钟

回溯法迷宫问题

思路：利用回溯法和递归思想解决。

findWay 方法就是专门来找出迷宫的路径
如果找到，就返回 true ,否则返回 false
map 就是二维数组，即表示迷宫
i,j 就是老鼠的位置，初始化的位置为(1,1)
因为我们是递归的找路，所以我先规定 map 数组的各个值的含义==0 表示可以走 1 表示障碍物 2 表示可以走 3 表示走过，但是走不通是死路==
递归出口当 map[6][5] =2 就说明找到通路,就可以结束，否则就继续找
先确定老鼠找路策略 ==下->右->上->左==

public class migong{  public static void main(String args[]){    int [][]map = new int[8][7];        //迷宫为一个八行七列的二维数组，墙为1，路为0    for(int i=0;i<7;i++){      map[0][i] = 1;      map[7][i] = 1;    }    for(int i = 0;i<8;i++){      map[i][0] = 1;      map[i][6] = 1;    }    //设计迷宫四周的墙    map[3][1] = 1;    map[3][2] = 1;    map[3][3] = 1;    map[2][3] = 1;    map[2][1] = 1;    //设置迷宫图形    System.out.println("当前地图：");  for(int i = 0;i<map.length;i++){    for(int j = 0;j<map[i].length;j++){      System.out.print(map[i][j] + " ");    }    System.out.println();  }//遍历一遍数组，即打印初始迷宫
  Dfs d = new Dfs();  d.findWay(map,1,1);    //实例化对象并调用递归方法  System.out.println("走后地图：");  for(int i = 0;i<map.length;i++){    for(int j = 0;j<map[i].length;j++){      System.out.print(map[i][j] + " ");    }    System.out.println();  }  //打印跑后的迷宫图
}}class Dfs{  public boolean findWay(int[][]map,int i,int j){    if(map[6][5] == 2){      return true;      //递归出口，即走到6,5位置    }else{      if(map[i][j] == 0){        map[i][j]=2;        //可以行通赋值为2            if(findWay(map,i+1,j)){        return true;      }else if(findWay(map,i,j+1)){        return true;      }else if(findWay(map,i-1,j)){        return true;      }else if(findWay(map,i,j-1)){        return true;      }      else{        map[i][j] = 3;        return false;        //若走不通则赋值为3      }    }    else{      return false;    }    }  }}