数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究算法问题 - 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
更新于: 2020-11-21
148 次浏览
广告