使用 DFS 的算法

Question

我正在尝试解决这个问题，它卡在了一个循环中，但我不明白为什么。我想我可能需要添加更多条件，我也看过其他人的代码，但它们似乎太复杂了。

    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
    }

Answer 1

问题是你没有标记你访问过哪些单元格，所以你会再次访问同一个单元格，导致坐标 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
    // ...

其他一些问题：

你应该以调用者知道递归搜索是否成功的方式实现回溯。因此，让您的函数 return 表明这一点，例如布尔值。只有当 return 值为真时，退出。否则，仍应尝试替代方向，如果不存在替代方向，弹出应该以 return 为 false 的方式发生。此外，基本情况应 return 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 并在函数的 start 处检查后续的 push，而不是在之前（递归）调用。

Answer 2

这是当前问题的解决方案，由 Mr. 创建。特林科。实现是在 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

使用 DFS 的算法

Algorithm using DFS

depth-first-search