Tìm đường đến cuối mê cung bằng JavaScript

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript có một ma trận có thứ tự N * N. Các bức tường trong ma trận được đánh dấu bằng ‘W’ và các vị trí trống được đánh dấu bằng ‘_’

Chúng ta có thể di chuyển theo bất kỳ hướng nào trong bốn hướng tại bất kỳ thời điểm nào. Hàm của chúng ta sẽ trả về true nếu chúng ta có thể đạt đến cuối [N - 1, N - 1], ngược lại là false.

Ví dụ

Sau đây là mã -

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));

Đầu ra

true