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

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một ma trận bậc N * N. Các tường trong ma trận được đánh dấu bằng 'W' và vị trí trống được đánh dấu bằng '_'. Chúng ta có thể di chuyển theo 4 hướng tại bất kỳ điểm nào. Hàm sẽ trả về true nếu có thể đến đích [N - 1, N - 1], ngược lại false.

Ví dụ

Dưới đây là mã nguồn:

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

Kết quả

true