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输入参数中使用数据结构（例如向量）记录当前路径，并且当DFS可以到达末端时，请标记矢量中的所有坐标。感叹点。

Answer 2

顺便说一下，它被称为深度优先搜索，而不是“深度过滤搜索”。

Answer 3

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