資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告