ค้นหาเส้นทางไปยังจุดสิ้นสุดของเขาวงกตโดยใช้ JavaScript

ปัญหา

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับเมทริกซ์ของลำดับ N * N ผนังในเมทริกซ์ถูกทำเครื่องหมายด้วย 'W' และตำแหน่งว่างจะถูกทำเครื่องหมายด้วย '_'

เราสามารถเคลื่อนที่ไปในทิศทางใดก็ได้จากสี่ทิศทาง ณ จุดใดก็ได้ ฟังก์ชันของเราควรคืนค่าเป็น จริง หากเราสามารถไปถึงจุดสิ้นสุด [N - 1, N - 1] ไม่เช่นนั้นเป็นเท็จ

ตัวอย่าง

ต่อไปนี้เป็นรหัส -

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