The dfs is not wroking

Question

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?

Answer 1

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.