DFS 矩阵的正确方法是什么？
Which is the proper way to DFS a matrix?
我做这道练习题是为了找出一个词是否存在于矩阵中，这让我意识到我并不完全理解 DFS。
在 Cracking the Coding Interview 中，DFS 的伪代码是：
void search(Node root) {
if (root == null) return;
visit(root);
root.visited = true;
for each (Node n in root.adjacent) {
if (n.visited == false) {
search(n);
}
}
}
对我来说，这看起来像这样的格式：
- 目标
- 标记
- 循环
- 如果邻居不满足条件，请提前保释
- 递归
所以用这种格式，我写了函数dfs():
function dfs(r, c, i) {
// goal
if (i === word.length-1) return true;
// mark
board[r][c] = '#';
// loop and recurse each neighbor
for (var d of dirs) {
var nr = r + d[0];
var nc = c + d[1];
// bail early if neighbor does not meet conditions
if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue; // neighbor is out of bounds
if (board[nr][nc] === '#') continue; // neighbor already visited
if (board[nr][nc] !== word[i+1]) continue; // neighbor does not meet goal
// recursion
var result = dfs(nr, nc, i+1);
// un-mark
board[r][c] = word[i];
return result;
}
}
其次，我注意到大多数解决方案根本不使用 for 循环，而只是为每个邻居编写 4 次递归。考虑到这一点，我写道 dfs2():
- 目标
- 如果当前节点不满足条件，则提前退出
- 标记
递归
function dfs2(r, c, i) {
// goal
if (i === word.length) return true;
// bail early if current does not meet conditions
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false; // current is out of bounds
if (board[r][c] === '#') return false; // current already visited
if (board[r][c] !== word[i]) return false; // current does not meet goal
// mark
board[r][c] = '#';
// recursion
var result = dfs2(r+1, c, i+1) || dfs2(r-1, c, i+1) || dfs2(r, c+1, i+1) || dfs2(r, c-1, i+1);
// un-mark
board[r][c] = word[i];
return result;
}
这更简洁，但对我来说更难理解。第一个版本 dfs() 做了一个循环，并在递归之前早早地在邻居上退出，这对我来说更有意义。 "If the neighbor is bad, don't go there." 第二个版本没有循环，所以它会在当前节点上进行所有检查。
我注意到的第一件事是，在大多数涉及网格的问题中，解决方案在递归之后涉及 "un-marking"。为什么是这样？这是否仅适用于 "word search problem" 等特定情况，您可能希望将来以不同的路径重新访问该节点？
哪个是正确的，dfs()还是dfs2()？
https://repl.it/MSCw/0
这是全部内容：
var dirs = [
[0,1], // r
[1,0], // d
[0,-1], // u
[-1,0], // l
];
var wsBoard = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
];
var exist = function(board, word, version) {
for (var r = 0; r < board.length; r++) {
for (var c = 0; c < board[0].length; c++) {
if (board[r][c] === word[0])
if (dfs(r, c, 0)) return true;
// if (dfs2(r, c, 0)) return true;
}
}
return false;
function dfs(r, c, i) {
console.log(`(${r},${c})\t${i}: ${word[i]}`);
// goal
if (i === word.length-1) return true;
// mark
board[r][c] = '#';
// loop and recurse each neighbor
for (var d of dirs) {
var nr = r + d[0];
var nc = c + d[1];
// bail early if neighbor does not meet conditions
if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue; // neighbor is out of bounds
if (board[nr][nc] === '#') continue; // neighbor already visited
if (board[nr][nc] !== word[i+1]) continue; // neighbor does not meet goal
console.log(board);
// recursion
var result = dfs(nr, nc, i+1);
// un-mark
board[r][c] = word[i];
return result;
}
}
function dfs2(r, c, i) {
console.log(`(${r},${c})\t${i}: ${word[i]}`);
// goal
if (i === word.length) return true;
// bail early if current does not meet conditions
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false; // current is out of bounds
if (board[r][c] === '#') return false; // current already visited
if (board[r][c] !== word[i]) return false; // current does not meet goal
// mark
board[r][c] = '#';
console.log(board);
// recursion
var result = dfs2(r+1, c, i+1) || dfs2(r-1, c, i+1) || dfs2(r, c+1, i+1) || dfs2(r, c-1, i+1);
// un-mark
board[r][c] = word[i];
return result;
}
};
console.log(exist(wsBoard, 'ABCCED')); // => true
console.log(exist(wsBoard, 'SEE')); // => true
console.log(exist(wsBoard, 'ABCB')); // => false
我认为即使 dfs 和 dfs2 都基于相同的想法 dfs 有一个缺陷，它是 return 探索的结果仅限第一条路径！
看看这个例子，我试图在看板中找到 FOO，很明显，它是第一列，但是你的实现 returns false
var dirs = [
[0,1], // r
[1,0], // d
[0,-1], // u
[-1,0], // l
];
var board = [
['F','O','X'],
['O',' ',' '],
['O',' ',' ']
];
var exist = function(word) {
function dfs(r, c, i) {
// mark
board[r][c] = '#';
// goal
if (i === word.length-1) return true;
// loop and recurse each neighbor
for (var d of dirs) {
var nr = r + d[0];
var nc = c + d[1];
// bail early if neighbor does not meet conditions
if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue; // neighbor is out of bounds
if (board[nr][nc] === '#') continue; // neighbor already visited
if (board[nr][nc] !== word[i+1]) continue; // neighbor does not meet goal
// recursion
var result = dfs(nr, nc, i+1);
// un-mark
board[r][c] = word[i];
return result;
}
}
for (var r = 0; r < board.length; r++) {
for (var c = 0; c < board[0].length; c++) {
if (board[r][c] === word[0]) {}
if (dfs(r, c, 0)) return true;
}
}
return false;
}
console.log(exist('FOO'))
问题是你的 for 循环总是 return 第一次递归的结果，要解决这个问题，让我们将 result 移到循环之外，使其成为 false 并在找到有效路径后使其采用 true 的值。
var dirs = [
[0,1], // r
[1,0], // d
[0,-1], // u
[-1,0], // l
];
var board = [
['F','O','X'],
['O',' ',' '],
['O',' ',' ']
];
var exist = function(word) {
function dfs(r, c, i) {
// mark
board[r][c] = '#';
// goal
if (i === word.length-1) return true;
// assume that there's no valid path initially
var result = false
// loop and recurse each neighbor
for (var d of dirs) {
var nr = r + d[0];
var nc = c + d[1];
// bail early if neighbor does not meet conditions
if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue; // neighbor is out of bounds
if (board[nr][nc] === '#') continue; // neighbor already visited
if (board[nr][nc] !== word[i+1]) continue; // neighbor does not meet goal
// recursion
result = result || dfs(nr, nc, i+1);
}
// un-mark
board[r][c] = word[i];
return result;
}
for (var r = 0; r < board.length; r++) {
for (var c = 0; c < board[0].length; c++) {
if (board[r][c] === word[0]) {}
if (dfs(r, c, 0)) return true;
}
}
return false;
}
console.log(exist('FOO'))
如果我们查看 dfs2，唯一的区别是 for 循环被展开，例如
var result = false;
for (var dir in dirs) {
// ...
result = result || dfs(nr, nc, i+1)
}
return result;
// becomes
var result = dfs2(...) || dfs2(...) || ...
The first things that I noticed was that in most problems involving a grid, solutions involve "un-marking" after the recursion. Why is this?
在某些解决方案中，您实际上可能会改变您正在使用的对象，例如在另一个经典问题中，该问题是找到一个单词的所有排列，您可以通过递归地改变单词来解决它，在一个排列之后发现下一个递归调用将使用不同的状态（这是不希望的），此问题中的 unmarking 概念被转换为将单词转换为其先前状态的还原操作。
Which is correct, dfs() or dfs2()?
两者都是正确的（好吧，在 dfs 被修复之后），但是，dfs2 会递归到无效状态，例如越界单元格或不属于单词的单元格，就复杂性而言，这种额外的开销只是一个常数乘数，例如即使你想象你从每个单元格访问每个邻居，复杂度也是 O(4 * # rows * # columns)
我做这道练习题是为了找出一个词是否存在于矩阵中，这让我意识到我并不完全理解 DFS。
在 Cracking the Coding Interview 中，DFS 的伪代码是：
void search(Node root) {
if (root == null) return;
visit(root);
root.visited = true;
for each (Node n in root.adjacent) {
if (n.visited == false) {
search(n);
}
}
}
对我来说，这看起来像这样的格式：
- 目标
- 标记
- 循环
- 如果邻居不满足条件，请提前保释
- 递归
所以用这种格式，我写了函数dfs():
function dfs(r, c, i) {
// goal
if (i === word.length-1) return true;
// mark
board[r][c] = '#';
// loop and recurse each neighbor
for (var d of dirs) {
var nr = r + d[0];
var nc = c + d[1];
// bail early if neighbor does not meet conditions
if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue; // neighbor is out of bounds
if (board[nr][nc] === '#') continue; // neighbor already visited
if (board[nr][nc] !== word[i+1]) continue; // neighbor does not meet goal
// recursion
var result = dfs(nr, nc, i+1);
// un-mark
board[r][c] = word[i];
return result;
}
}
其次，我注意到大多数解决方案根本不使用 for 循环，而只是为每个邻居编写 4 次递归。考虑到这一点，我写道 dfs2():
- 目标
- 如果当前节点不满足条件，则提前退出
- 标记
递归
function dfs2(r, c, i) { // goal if (i === word.length) return true; // bail early if current does not meet conditions if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false; // current is out of bounds if (board[r][c] === '#') return false; // current already visited if (board[r][c] !== word[i]) return false; // current does not meet goal // mark board[r][c] = '#'; // recursion var result = dfs2(r+1, c, i+1) || dfs2(r-1, c, i+1) || dfs2(r, c+1, i+1) || dfs2(r, c-1, i+1); // un-mark board[r][c] = word[i]; return result; }
这更简洁，但对我来说更难理解。第一个版本 dfs() 做了一个循环，并在递归之前早早地在邻居上退出，这对我来说更有意义。 "If the neighbor is bad, don't go there." 第二个版本没有循环，所以它会在当前节点上进行所有检查。
我注意到的第一件事是，在大多数涉及网格的问题中，解决方案在递归之后涉及 "un-marking"。为什么是这样？这是否仅适用于 "word search problem" 等特定情况，您可能希望将来以不同的路径重新访问该节点？
哪个是正确的，dfs()还是dfs2()？
https://repl.it/MSCw/0 这是全部内容：
var dirs = [
[0,1], // r
[1,0], // d
[0,-1], // u
[-1,0], // l
];
var wsBoard = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
];
var exist = function(board, word, version) {
for (var r = 0; r < board.length; r++) {
for (var c = 0; c < board[0].length; c++) {
if (board[r][c] === word[0])
if (dfs(r, c, 0)) return true;
// if (dfs2(r, c, 0)) return true;
}
}
return false;
function dfs(r, c, i) {
console.log(`(${r},${c})\t${i}: ${word[i]}`);
// goal
if (i === word.length-1) return true;
// mark
board[r][c] = '#';
// loop and recurse each neighbor
for (var d of dirs) {
var nr = r + d[0];
var nc = c + d[1];
// bail early if neighbor does not meet conditions
if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue; // neighbor is out of bounds
if (board[nr][nc] === '#') continue; // neighbor already visited
if (board[nr][nc] !== word[i+1]) continue; // neighbor does not meet goal
console.log(board);
// recursion
var result = dfs(nr, nc, i+1);
// un-mark
board[r][c] = word[i];
return result;
}
}
function dfs2(r, c, i) {
console.log(`(${r},${c})\t${i}: ${word[i]}`);
// goal
if (i === word.length) return true;
// bail early if current does not meet conditions
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length) return false; // current is out of bounds
if (board[r][c] === '#') return false; // current already visited
if (board[r][c] !== word[i]) return false; // current does not meet goal
// mark
board[r][c] = '#';
console.log(board);
// recursion
var result = dfs2(r+1, c, i+1) || dfs2(r-1, c, i+1) || dfs2(r, c+1, i+1) || dfs2(r, c-1, i+1);
// un-mark
board[r][c] = word[i];
return result;
}
};
console.log(exist(wsBoard, 'ABCCED')); // => true
console.log(exist(wsBoard, 'SEE')); // => true
console.log(exist(wsBoard, 'ABCB')); // => false
我认为即使 dfs 和 dfs2 都基于相同的想法 dfs 有一个缺陷，它是 return 探索的结果仅限第一条路径！
看看这个例子，我试图在看板中找到 FOO，很明显，它是第一列，但是你的实现 returns false
var dirs = [
[0,1], // r
[1,0], // d
[0,-1], // u
[-1,0], // l
];
var board = [
['F','O','X'],
['O',' ',' '],
['O',' ',' ']
];
var exist = function(word) {
function dfs(r, c, i) {
// mark
board[r][c] = '#';
// goal
if (i === word.length-1) return true;
// loop and recurse each neighbor
for (var d of dirs) {
var nr = r + d[0];
var nc = c + d[1];
// bail early if neighbor does not meet conditions
if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue; // neighbor is out of bounds
if (board[nr][nc] === '#') continue; // neighbor already visited
if (board[nr][nc] !== word[i+1]) continue; // neighbor does not meet goal
// recursion
var result = dfs(nr, nc, i+1);
// un-mark
board[r][c] = word[i];
return result;
}
}
for (var r = 0; r < board.length; r++) {
for (var c = 0; c < board[0].length; c++) {
if (board[r][c] === word[0]) {}
if (dfs(r, c, 0)) return true;
}
}
return false;
}
console.log(exist('FOO'))
问题是你的 for 循环总是 return 第一次递归的结果，要解决这个问题，让我们将 result 移到循环之外，使其成为 false 并在找到有效路径后使其采用 true 的值。
var dirs = [
[0,1], // r
[1,0], // d
[0,-1], // u
[-1,0], // l
];
var board = [
['F','O','X'],
['O',' ',' '],
['O',' ',' ']
];
var exist = function(word) {
function dfs(r, c, i) {
// mark
board[r][c] = '#';
// goal
if (i === word.length-1) return true;
// assume that there's no valid path initially
var result = false
// loop and recurse each neighbor
for (var d of dirs) {
var nr = r + d[0];
var nc = c + d[1];
// bail early if neighbor does not meet conditions
if (nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) continue; // neighbor is out of bounds
if (board[nr][nc] === '#') continue; // neighbor already visited
if (board[nr][nc] !== word[i+1]) continue; // neighbor does not meet goal
// recursion
result = result || dfs(nr, nc, i+1);
}
// un-mark
board[r][c] = word[i];
return result;
}
for (var r = 0; r < board.length; r++) {
for (var c = 0; c < board[0].length; c++) {
if (board[r][c] === word[0]) {}
if (dfs(r, c, 0)) return true;
}
}
return false;
}
console.log(exist('FOO'))
如果我们查看 dfs2，唯一的区别是 for 循环被展开，例如
var result = false;
for (var dir in dirs) {
// ...
result = result || dfs(nr, nc, i+1)
}
return result;
// becomes
var result = dfs2(...) || dfs2(...) || ...
The first things that I noticed was that in most problems involving a grid, solutions involve "un-marking" after the recursion. Why is this?
在某些解决方案中，您实际上可能会改变您正在使用的对象，例如在另一个经典问题中，该问题是找到一个单词的所有排列，您可以通过递归地改变单词来解决它，在一个排列之后发现下一个递归调用将使用不同的状态（这是不希望的），此问题中的 unmarking 概念被转换为将单词转换为其先前状态的还原操作。
Which is correct, dfs() or dfs2()?
两者都是正确的（好吧，在 dfs 被修复之后），但是，dfs2 会递归到无效状态，例如越界单元格或不属于单词的单元格，就复杂性而言，这种额外的开销只是一个常数乘数，例如即使你想象你从每个单元格访问每个邻居，复杂度也是 O(4 * # rows * # columns)