题解 | #迷宫问题#

// 贡献一道js的广度优先搜索解法，看了js题解下面很少有广度优先的解法
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// 这道题目说的是只能横着走或者竖着走，没说只能向下或者向右，所以这道题向左或者向上走都是可以的，这里面临的问题就是可能会走到已经走过的地方（这里会无限循环下去，如果可以走回头路）。所以需要给每个走过的地方都标记，不允许再次走
// 深度优先搜索
/*function maze_path(arr) {
  let ans = [];
  let i = 0,
    j = 0;
  function dfs(i, j) {
    if(i < 0 || i > arr.length - 1 || arr[i][j] === 1 || arr[i][j] === undefined){
      return
    }
    ans.push(`(${i},${j})`);
    arr[i][j]=1 // 这里将遍历过的每个元素掷为1，也就是标记了已经走过的意思，下次不允许再走回头路。
    if (i === arr.length - 1 && j === arr[0].length - 1) {
      for (const item of ans) {
        console.log(item);
      }
      return;
    }
    let index = ans.length - 1;
    dfs(i, j + 1); // 向右走
    ans.splice(index + 1);
    dfs(i + 1, j); // 向下走
    ans.splice(index + 1);
    dfs(i-1, j); // 向上走
    ans.splice(index + 1);
    dfs(i, j-1); // 向左走
    ans.splice(index + 1);
  }
  dfs(0, 0);
}*/

// 广度优先搜索
function maze_path(arr) {
  let x1 = 0,x2 = arr.length-1,y1 = 0,y2 = arr[0].length-1
  const queue = []
  // 定义一个数组，来记录每一个点的上一个点的位置，方便后续找出点的位置。
  const path = []
  queue.push([x1,y1,-1])
  while(queue.length){
    let curNode = queue.shift()
    path.push(curNode);
    let [i,j] = curNode;
    // let i = curNode[0],j = curNode[1]
    // 到达终点
    if(curNode[0] === x2 && curNode[1] === y2){
      const realPath = []
      // 根据每一个当前的点找到它的上一个节点，循环完后再翻转，因为这是倒着的。
      while(curNode[2] !== -1){
        realPath.push(`(${curNode[0]},${curNode[1]})`)
        curNode = path[curNode[2]]
      }
      realPath.push(`(${curNode[0]},${curNode[1]})`)
      realPath.reverse()
      for(const item of realPath){
        console.log(item)
      }
      return
    }
    arr[i][j] = 1
    i > 0 && arr[i-1][j] === 0 && queue.push([i-1,j,path.length-1]) // 向上
    arr[i][j+1] === 0 && queue.push([i,j+1,path.length-1]) // 向右
    i < x2 && arr[i+1][j] === 0 && queue.push([i+1,j,path.length-1]) // 向下
    arr[i][j-1] === 0 && queue.push([i,j-1,path.length-1]) // 向左
  }
}



const arr = [];
rl.on("line", function (line) {
  arr.push(line.split(" ").map((item) => parseInt(item)));
});
rl.on("close", function () {
  arr.shift()
  maze_path(arr);
});