使用DFS的算法
使用DFS的算法
提问于 2021-11-25 17:15:39
我试图解决这个问题，它被困在一个循环中，但我不明白为什么。我想我可能需要添加一些更多的条件，我已经查看了其他人的代码，但它们看起来太复杂了。
function solve(m, s, x, y) {
if (x == 9 && m[x][y] == "1")
{return;} //if last row, found door
if (m[x+1][y] == "1") { //down
s.push([x+1] + ", " + [y]);
solve(m, s, x+1, y);
}
if (m[x][y+1] == "1") { //left
s.push([x] + ", " + [y+1]);
solve(m, s, x, y+1);
}
if (m[x][y-1] == "1") { //right
s.push([x] + ", " + [y-1]);
solve(m, s, x, y-1);
}
if (matrix[x-1][y] == "1") { //up
s.push([x-1] + ", " + [y]);
solve(m, s, x-1, y);
}
s.pop(); //if bad path with no end
}Stack Overflow用户
回答已采纳
发布于 2021-11-25 18:13:29
问题是，您没有标记您访问过的单元格，因此您将再次访问同一个单元格，从而导致在坐标4、8和4,9之间的无结束的来回时间。
解决这一问题的一种方法是在矩阵中留下一个带有另一个值的跟踪，如值2：
// ...
if (x == 9 && matrix[x][y] == "1") {
{ return; } //if last row, found door
matrix[x][y] = 2; // mark as visited <-- add this
// ...其他一些问题：
- 您应该以调用者知道递归搜索是否成功的方式实现回溯。因此，让您的函数返回一些指示这一点的内容，比如布尔值。只有当返回值为真时，才退出。否则，仍应尝试其他方向，如果没有其他选择，则pop应返回false。此外，基本大小写应该返回true或false。
- 范围检查不应使用文字(如
9)，而应是动态的，因此它们检查输入数组的实际大小.
let stack = [];
let matrix = [
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 0],
[1, 1, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0],
];
function solve(matrix, stack, x, y) {
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) {
return false;
}
if (x == matrix.length - 1 && matrix[x][y] == "1") {
return true; //if last row, found door
}
matrix[x][y] = 2; // mark as visited
if (matrix[x+1][y] == "1") { //down
stack.push([x+1] + ", " + [y]);
if (solve(matrix, stack, x+1, y)) return true;
}
if (matrix[x][y+1] == "1") { //left
stack.push([x] + ", " + [y+1]);
if (solve(matrix, stack, x, y+1)) return true;
}
if (matrix[x][y-1] == "1") { //right
stack.push([x] + ", " + [y-1]);
if (solve(matrix, stack, x, y-1)) return true;
}
if (matrix[x-1][y] == "1") { //up
stack.push([x-1] + ", " + [y]);
if (solve(matrix, stack, x-1, y)) return true;
}
stack.pop(); //if bad path with no end
return false;
}
function detectStart(matrix, stack) {
for (let y = 0; y < matrix.length; y++) {
if (matrix[0][y] === 1) {
stack.push([0] + ", " + [y]);
solve(matrix, stack, 0, y);
console.log(stack);
return;
}
}
}
detectStart(matrix, stack);
其他一些评论：
- 比较矩阵值和字符串，而用数值初始化矩阵，这有点奇怪。
- 您可以避免代码重复，并在函数开始时检查单元格中的1和随后的
push，而不是在(递归)调用.
之前进行检查。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/70115066
复制相关文章
相似问题
腾讯云开发者
