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

请看以下回溯问题：在二维网格上，有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));

说明

• 我们设置变量以方便在遍历网格时进行四向迭代，对矩阵中的零进行计数，以便在达到递归的基本条件时检查覆盖率

• 然后，我们设置DFS（深度优先搜索）回溯功能，以在活动路径上用-1标记网格，并在到达终点单元时检查路径长度

• 最后，我们从起始单元启动DFS以计数所有完整路径并返回计数

输出结果

控制台中的输出将是-

2