JS实现“老鼠走迷宫”算法

问题描述

给定一个二维数组，数组中2表示墙壁，0表示通路，由此数组可展示为一个迷宫图。给定入口位置和出口位置，判断之间是否存在通路并显示出走出迷宫的道路。

思路

实际上是使用回溯算法求解该问题，就是在上下左右四个方向试探，倘若有路则走一步，在新的位置继续在四个位置试探，并且对走过的路进行标记，倘若走到死胡同里，则退回上一步再来试探，以此类推，使用递归来实现。

JS代码

//递归实现老鼠走迷宫算法
// 定义的迷宫
let maze = [["2","2","2","2","2","2","2","2","2"],  ["2","0","0","0","0","0","0","0","2"],  ["2","0","2","2","0","2","2","0","2"],  ["2","0","2","0","0","2","0","0","2"],  ["2","0","2","0","2","0","2","0","2"],  ["2","0","0","0","0","0","2","0","2"],  ["2","2","2","2","2","2","2","0","2"],  ["2","0","0","0","0","0","0","0","2"],  ["2","2","2","2","2","2","2","0","2"]  
] 
begin_x = 1;           //迷宫入口横坐标
begin_y = 1;           //迷宫入口纵坐标
end_x = 8;             //迷宫出口横坐标
end_y = 7;             //迷宫出口纵坐标
let flag = false;      //定义标志位，判断老鼠有没有出迷宫
let total = 0;         //有多少条路线可以出去
let loop = maze.slice(0);  //数组深拷贝，用于绘制路线。切忌maze_loop = maze;这是浅拷贝。 //设计算法让老鼠移动
function findLoop(arr,start_x,start_y){arr[start_x][start_y] = 1;    //走一步做一个标记，表明已经走过这个格子了，不能走这个格子，只能往下走。loop[start_x][start_y] = '#'; //标记路线//到达迷宫出口if((start_x===end_x)&&(start_y===end_y)){flag=true;console.log(loop);  //打印迷宫路线}else if(flag!==true){try{//定义上 下 左 右移动if(arr[start_x][start_y-1]==0&&!flag){findLoop(arr,start_x,start_y-1)}if(arr[start_x][start_y+1]==0&&!flag){findLoop(arr,start_x,start_y+1)}if(arr[start_x-1][start_y]==0&&!flag){findLoop(arr,start_x-1,start_y)}if(arr[start_x+1][start_y]==0&&!flag){findLoop(arr,start_x+1,start_y)}if(!flag){//如果走不通了，我就倒回去，把最开始的标记清除。重新选择另一条路。loop[start_x][start_y] = "0";arr[start_x][start_y] = "0";}}catch(error){//避免因没有找到出去的路，而造成死循环,堆栈溢出console.log('这个迷宫没有出路',error);}}return flag==false?'真遗憾,小老鼠走不出去了':'小老鼠成功走出迷宫';
}
findLoop(maze,begin_x,begin_y)

结果

其中"#"表示小老鼠走出去的路线