使用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
}回答 2
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用户
发布于 2021-12-18 11:42:31
以下是当前问题的解决方案，由先生trincot先生创建。该实现是在C++中实现的。
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int maximumSize=6;
vector<vector<int>> 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}};
vector<vector<int>> visited(maximumSize, vector<int>(maximumSize, 0));
vector<tuple<int, int>> path;
void showContentVector2D(vector<vector<int>>& input)
{
for(int i=0; i<input.size(); ++i)
{
for(int j=0; j<input[i].size(); ++j)
{
cout<<input[i][j]<<", ";
}
cout<<endl;
}
return;
}
void showContentVectorTuple(vector<tuple<int, int>>& input)
{
for(int i=0; i<input.size(); ++i)
{
cout<<get<0>(input[i])<<" : "<<get<1>(input[i])<<endl;
}
return;
}
void dfs(int indexX, int indexY)
{
if(indexX<0 || indexX==matrix.size() || indexY<0 || indexY==matrix[0].size())
{
return;
}
if(indexX==(matrix.size()-1) && (matrix[indexX][indexY]==1))
{
visited[indexX][indexY]=1;
auto indices=make_tuple(indexX, indexY);
path.push_back(indices);
return;
}
visited[indexX][indexY]=1;
auto indices=make_tuple(indexX, indexY);
path.push_back(indices);
if(visited[indexX+1][indexY]==0)
{
if(matrix[indexX+1][indexY]==1)
{
dfs(indexX+1, indexY);
if(visited[indexX+1][indexY])
{
return;
}
}
}
if(visited[indexX-1][indexY]==0)
{
if(matrix[indexX-1][indexY]==1)
{
dfs(indexX-1, indexY);
if(visited[indexX-1][indexY])
{
return;
}
}
}
if(visited[indexX][indexY-1]==0)
{
if(matrix[indexX][indexY-1]==1)
{
dfs(indexX, indexY-1);
if(visited[indexX][indexY-1])
{
return;
}
}
}
if(visited[indexX][indexY+1]==0)
{
if(matrix[indexX][indexY+1]==1)
{
dfs(indexX, indexY+1);
if(visited[indexX][indexY+1])
{
return;
}
}
}
return;
}
void solve()
{
for(int i=0; i<matrix.size(); ++i)
{
if(matrix[0][i]==1)
{
dfs(0, i);
}
}
cout<<"visited <- "<<endl;
showContentVector2D(visited);
cout<<endl<<"matrix <- "<<endl;
showContentVector2D(matrix);
cout<<endl<<"path <- "<<endl;
showContentVectorTuple(path);
cout<<endl;
return;
}
int main()
{
solve();
return 0;
}结果如下：
visited <-
0, 1, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0,
1, 1, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0,
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,
path <-
0 : 1
1 : 1
2 : 1
3 : 1
3 : 0
4 : 0
5 : 0页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/70115066
复制相关文章
相似问题
腾讯云开发者
