The dfs is not wroking-CodePudding

The problem I am seeing is that it outputted all of the ways, even the ones that cannot reach the end. But that is not how DFS is supposed to work.

As I know right now, DFS is within a recursive call chain, and when it goes deeper into the function, it should remove the ones that are not correct and keep the ones that are correct.

Here is the code:

#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;
}

The input is like this:

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

And the output:

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

Does anyone know why this is happening?

CodePudding user response：

Herein lies the problem, all locations visited by DFS are marked:

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

You should record the current path with a data structure (such as vector) in the DFS input parameter, and when DFS can reach the end, mark all coordinates in the vector with an exclamation point.

CodePudding user response：

By the way, it's called Depth-First Search, not "deep filtering search".

CodePudding user response：

The path you want to search is 17 squares, which is the shortest, and the other paths are shorter than that, so all the paths will be searched.