1、第一步初始化迷宫
2、第二步递归回溯 递归回溯分为三步:
1、return的条件,该题可知当到达目的地时即可return
2、递归,此题需要注意的是方向,可以上下左右四个方向,当上一次是下时,那么此时不能向上,那么就会循环调用上上下下形成死循环
3、回溯,将改变的条件进行回溯 3、打印结果,遍历一遍结果即可
let line1= readline().split(' ').map(Number);
let arrs=[]
while(line = readline()){
arrs.push(line.split(' '))
}
function goPath(){
let ans=[]
const dfs=(arr,x,y)=>{
// console.log(arr,x,y)
if(x==line1[0]-1&&y==line1[1]-1){
arr.push(`(${x},${y})`)
return ans.push(arr.slice())
}
// 包含重复路径会死循环
if(arr.includes(`(${x},${y})`)) return
if(arrs[x][y]==0){
arr.push(`(${x},${y})`)
if(x<line1[0]-1&&arrs[x+1][y]==0) dfs(arr.slice(),x+1,y);
if(y<line1[1]-1&&arrs[x][y+1]==0) dfs(arr.slice(),x,y+1);
if(x>0&&arrs[x-1][y]==0) dfs(arr.slice(),x-1,y);
if(y>0&&arrs[x][y-1]==0) dfs(arr.slice(),x,y-1);
}
}
dfs([],0,0)
// console.log(ans)
return ans
}
goPath()
[0].map(item=>{
console.log(item)
})

京公网安备 11010502036488号