dfs 不工作

Question

我看到的问题是输出了所有方式，甚至是无法达到的方式结束。 但这不是 DFS 应有的工作方式。

据我所知，DFS在递归调用链中，当它深入到函数中时，它应该删除 不正确的 并保留正确的。

代码如下：

#include <iostream>
#define ll long long
using namespace std;
bool f = false;
ll map[10001][10001];
ll vis[10001][10001];
char endmap[10001][10001];
ll dx[] = {0 , 0 , 1 , -1};
ll dy[] = {-1, 1 , 0, 0};
ll n,m,x1,y1,x2,y2;
void dfs(ll fi, ll fj){
    if(fi == x2&&fj == y2){
        cout << "PATH FOUND!:" << endl;
        f = true;
        for(ll i1 = 1; i1<=n; i1++){
            for(ll j1 = 1; j1<= m; j1++){
                if(vis[i1][j1] == 1){
                    endmap[i1][j1] = '!';
                }
            }
        }
        endmap[1][1] = 'S';
        endmap[x2][y2] = 'E';
        for(ll i1 = 1; i1<=n; i1++){
            for(ll j1 = 1; j1<= m; j1++){
                cout << endmap[i1][j1] << " ";
            }
            cout << endl;
        }
        system("pause");
        exit(0);
    }else{
        for(ll i = 0; i<4; i++){
            ll xx = fi + dx[i];
            ll yy = fj + dy[i];
            if (yy>=1&& xx >= 1 && vis[xx][yy] == 0 && xx <= n && yy <= n && map[xx][yy] == 0){
                vis[xx][yy] = 1;
                dfs(xx,yy);
            }
        }
    }

}
int main(){
    cout << "Enter the length and the width of the map: ";
    cin >> n >> m;
    for(ll i = 1; i<=n; i++){
        for(ll j = 1; j<=m; j++){
            endmap[i][j] = '0';
        }
    }
    cout << "Draw the map: " << endl;
    for(ll i = 1; i<=n; i++){
        for(ll j = 1; j<=m; j++){
            cin >> map[i][j];
        }
    }
    cout << "Enter the start(two numbers) and the end(two numbers):";
    cin >> x1 >> y1 >> x2 >> y2;
    cout << endl << "EXECUTING..." << endl;
    dfs(x1,y1);
    if(!f){
        cerr << "ERROR! " << "Found on: " << __TIME__ << endl << "NO EXIT/PATH FOUND!" << endl;
    }
    return 0;
}

输入是这样的：

Enter the length and the width of the map: 9 9
Draw the map:
0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 0 1
1 0 0 0 1 0 0 0 1
1 0 1 0 1 0 1 0 1
1 0 0 1 1 1 1 0 1
1 1 0 1 1 1 1 1 1
1 1 0 0 0 0 1 1 1
1 1 1 1 1 0 0 0 0
Enter the start(two numbers) and the end(two numbers):1 1 9 9

并且输出：

EXECUTING...
PATH FOUND!:
S 0 0 0 0 0 0 0 0
! ! ! ! ! ! ! ! 0
0 ! 0 0 0 0 0 ! 0
0 ! ! ! 0 ! ! ! 0
0 ! 0 ! 0 ! 0 ! 0
0 ! ! 0 0 0 0 ! 0
0 0 ! 0 0 0 0 0 0
0 0 ! ! ! ! 0 0 0
0 0 0 0 0 ! ! ! E

有人知道为什么会这样吗？

Answer 1

问题就出在这里，DFS访问的所有位置都标出：

if(vis[i1][j1] == 1){
    endmap[i1][j1] = '!';
}

你应该在DFS输入参数中用一个数据结构（如vector）记录当前路径，当DFS到达终点时，在vector中的所有坐标用感叹号标记。

Answer 2

顺便说一句，它叫做Depth-First搜索，而不是“深度过滤搜索”。

Answer 3

你要搜索的路径是17格，这是最短的，其他路径都比它短，所以会搜索所有的路径。我认为有一种方法可以在不更改路线标记的情况下找到最短的路线。

dfs 不工作

The dfs is not wroking

c++

depth-first-search