算法问题 - JavaScript 中的回溯模式

javascriptfront end technologyobject oriented programmingweb development

考虑以下回溯问题:在二维网格上，有 4 种类型的方块 −

1 表示起始方块。起始方块只有一个。
2 表示终止方块。终止方块只有一个。
0 表示我们可以越过的空方块。
−1 表示我们不能越过的障碍物。

我们需要编写一个函数，返回从起始方块到终止方块的 4− 方向行走的次数，这些行走会越过每个非− 障碍物方块，且只行走一次。

示例

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