题解 | #迷宫问题#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  let lines = [];
  while ((line = await readline())) {
    lines.push(line);
  }
  let [n, m] = lines[0].split(" ").map((a) => parseInt(a));
  lines = lines.slice(1, lines.length);
  lines = lines.map((item) => {
    return item.split(" ");
  });
  // 迷宫问题适合用递归
  // 遍历每一条分叉，每一条路线均记录走过的路线，避免出现转圈，死循环
  let result = [];
  fn(0, 0, ["(0,0)"]);
  result[0].forEach((item) => {
    console.log(item);
  });
  function fn(a, b, stepHis) {
  	// 走到终点，分支结束，记录路线到集合
    if (a == n - 1 && b == m - 1) {
      result.push(stepHis);
      return false;
    }
	//  上下左右四条路
    let arry = [
      [a - 1, b],
      [a + 1, b],
      [a, b - 1],
      [a, b + 1],
    ];
    arry.forEach((item) => {
      let [x, y] = item;
      let step = "(" + x + "," + y + ")";
	  // 如果这一步已经走过，此分支结束
      if (stepHis.includes(step)) {
        return false;
      }
	  // 如果横向超越边界，分支结束
      if (x === -1 || x === n) {
        return false;
      }
	  // 纵向超越边界，分支结束
      if (y === m || -1 === y) {
        return false;
      }
	  // 此路撞墙，分支结束
      if (lines[x][y] == 1) {
        return false;
      }
      let his = [...stepHis];
      his.push(step);
	  // 向前走一步，并记录当前路线
      fn(x, y, his);
    });
  }
})();