所以這是在 0 和 1 的矩陣中找到從起始坐標到結束坐標的 1 的最長路徑的問題。
這是我以某種方式想出的解決方案，我也（幾乎）理解。雖然我無法理解其中的一行：
function longestPath02(matrix, startPosition, endPosition) {
let maxDistance = 0;
const visited = {};
function isValidCoordinate(i, j) {
// check if the coordinates are in valid range
// if (i < 0 || i > matrix.length - 1 || j > matrix[0].length - 1 || j < 0) return false;
if (i > matrix.length - 1 || i < 0 || j > matrix[0].length - 1 || j < 0) return false;
// check if the coordinate is one AND not visited
if ((matrix[i] || [])[j] !== 1 || visited[`${i},${j}`]) return false;
return true;
}
function calculate(startPosition, endPosition, distance) {
const [i, j] = startPosition;
const [x, y] = endPosition;
if (i === x && j === y) {
maxDistance = Math.max(distance, maxDistance);
return;
}
visited[`${i},${j}`] = true;
if (isValidCoordinate(i 1, j)) calculate([i 1, j], endPosition, distance 1);
if (isValidCoordinate(i - 1, j)) calculate([i - 1, j], endPosition, distance 1);
if (isValidCoordinate(i, j 1)) calculate([i, j 1], endPosition, distance 1);
if (isValidCoordinate(i, j - 1)) calculate([i, j - 1], endPosition, distance 1);
visited[`${i},${j}`] = false; // ??
}
calculate(startPosition, endPosition, 0);
return maxDistance;
}
無法理解為什么我們必須將訪問設定為 false！
沒有它，結果是不正確的。如何將訪問的坐標設定為假相關？
資料集：
let mat = [
[1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 1, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[1, 0, 0, 0, 1, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
[1, 1, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 0, 1, 0, 0],
];
console.log(longestPath02(mat, [0, 0], [5, 7]));
uj5u.com熱心網友回復：
如果我正確理解代碼，則突出顯示的行是回溯。
考慮這一行：visited[`${i},${j}`] = true;. 此行的目的是阻止遞回 DFS 訪問您剛剛訪問過的點（否則您將簡單地得到一個遞回回圈）。
但是一旦完成了該路徑，您需要“重置”，這就是您最終將其設定為 false 的原因。原因是否則，您將阻止未來的遞回呼叫訪問該元素！換句話說，一旦你完成了一條路徑，你需要釋放它，以便另一條路徑可以在需要時訪問該元素（否則該路徑會混淆并停止中途認為它已經訪問了一個元素，而實際上它已經訪問了一個元素。 t)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/497969.html
標籤：javascript 算法 矩阵 数据结构