（上图出自B站韩顺平教育）
从上图的(1,1)处，寻找到（6，5）处的路线，红色格子是障碍
public class MiGong {
public static void main(String[] args) {
//思路：
//1.先创建迷宫，用二维数组map表示
//2.规定数组的元素值：0表示可以走，1表示障碍
int[][] map=new int[8][7];
//3.将最上面的一行和最下面的一行全部设置为1
for (int i = 0; i < 7; i++) {
map[0][i]=1;
map[7][i]=1;
}
//4.将最右面的一列和最左面的一列全部设为1
for (int i = 0; i < 8; i++) {
map[i][0]=1;
map[i][6]=1;
}
//5.设置障碍物
map[3][1]=1;
map[3][2]=1;
//使用findWay
T t1 = new T();
t1.findWay(map,1,1);
System.out.println("=======找路的情况如下=========");
for (int[] ints : map) {
for (int anInt : ints) {
System.out.print(anInt+"\t");
}
System.out.println();
}
}
}
class T{
//使用递归回溯的思想来解决
//找到路径就返回true，否则false
//i,j就是老鼠的位置，初始化位置为(1,1)
//因为是递归找路，所以先规定may各个值的含义
// 0表示实际可以走的路 1表示障碍物 2表示探索时假设可以走的路，也是结果 3表示走过的路，但是死路
//当map[6][5] =2 表示找到路，可以结束，否则继续找
//先确定老鼠找路的策略 下->右->上->左
public boolean findWay(int[][] map,int i,int j){
if(map[6][5]==2){ //找到路
return true;
}else{
if(map[i][j] ==0) {//说明可以走
//先假设可以走通
map[i][j] = 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;
}
}else{
return false;
}
}
}
}
