使用 JavaScript 寻找迷宫尽头的路径

Z时代
2024-01-10
分类：综合

问题

我们需要编写一个 JavaScript 函数，该函数接受 N * N 阶矩阵。矩阵中的墙用“W”标记，空位置用“_”标记

我们可以在任何一点向四个方向中的任何一个方向移动。如果我们可以到达最后 [N - 1, N - 1]，我们的函数应该返回 true，否则返回 false。

示例

以下是代码 -

const maze = [
   ['_', 'W', 'W', 'W'],
   ['_', 'W', 'W', 'W'],
   ['W', '_', '_', 'W'],
   ['W', 'W', 'W', '_']
];
const canFindPath = (m = []) => {
   let h = m.length;
   let w = m[0].length;
   let queue = [[0, 0]];
   let mark = (xx, yy) => {
      [[1, 0], [-1, 0], [0, 1], [0, -1], [0, 0]].map(p => {
         let [x, y] = [p[0]+xx, p[1]+yy];
         if (0 <= x && x < w) {
            if (0 <= y && y < h) {
               if (m[y][x] === '.') {
                  m[y][x] = '#';
                  queue.push([x, y]);
               }
            }
         }
      });
   };
   do {
      let p = queue.shift();
      mark(...p);
   } while (queue.length);
   return m[h-1][w-1] !== '.';
};
console.log(canFindPath(maze));