Vấn đề thuật toán - Mẫu backtracking trong JavaScript

Xét bài toán backtracking sau: Trên lưới 2 chiều, có 4 loại ô:

• 1 đại diện ô bắt đầu. Có đúng một ô bắt đầu.
• 2 đại diện ô kết thúc. Có đúng một ô kết thúc.
• 0 đại diện ô trống có thể đi qua.
• -1 đại diện chướng ngại vật không thể đi qua.

Yêu cầu viết hàm trả về số lượng đường đi 4 chiều từ ô bắt đầu đến ô kết thúc, đi qua mọi ô không phải chướng ngại vật đúng một lần.

Ví dụ

const arr = [ 
  [1,0,0,0], 
  [0,0,0,0], 
  [0,0,2,-1] 
]; 
const uniquePaths = (arr, count = 0) => { 
  const dy = [1,-1,0,0], dx = [0,0,1,-1]; 
  const m = arr.length, n = arr[0].length; 
  const totalZeroes = arr.map(row => row.filter(num => num === 0).length).reduce((totalZeroes,nextRowZeroes) => totalZeroes + nextRowZeroes, 0); 
  const depthFirstSearch = (i, j, covered) => { 
    if (arr[i][j] === 2){ 
      if (covered === totalZeroes + 1) count++; 
      return; 
    }; 
    for (let k = 0; k < 4; k++) 
      if (i+dy[k] >= 0 && i+dy[k] < m && j+dx[k] >= 0 && j+dx[k] < n && arr[i+dy[k]][j+dx[k]] !== -1 ){ 
        arr[i][j] = -1; 
        depthFirstSearch(i+dy[k],j+dx[k],covered+1); 
        arr[i][j] = 0; 
      } 
    return; 
  }; 
  for (let row = 0; row < m; row++) 
    for (let col = 0; col < n; col++) 
      if (arr[row][col] === 1){ 
        arr[row][col] = -1; 
        depthFirstSearch(row,col,0); 
        break; 
      } 
  return count; 
}; 
console.log(uniquePaths(arr));

Giải thích

• Thiết lập biến cho lặp 4 hướng khi duyệt lưới, đếm số 0 trong ma trận để kiểm tra độ phủ khi điều kiện cơ sở đệ quy đạt đến
• Thiết lập hàm DFS (Tìm kiếm theo chiều sâu) backtrack đánh dấu lưới -1 trên đường đi active và kiểm tra độ dài đường khi đến ô kết thúc
• Khởi chạy DFS từ ô bắt đầu để đếm tất cả đường đi đầy đủ và trả về số lượng

Kết quả

Kết quả in ra console:

2