การหาเส้นทางไปยังปลายทางของเขาวงกตใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับเมทริกซ์ขนาด N×N ผนังในเมทริกซ์ถูกทำเครื่องหมายด้วย 'W' และตำแหน่งว่างด้วย '_' เราสามารถเคลื่อนที่ได้ 4 ทิศทางที่จุดใดๆ ฟังก์ชันควรคืนค่า true หากสามารถไปถึงปลายทาง [N-1, N-1] ได้ 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));

ผลลัพธ์

true