'The dfs is not wroking

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?

c++depth-first-search


Solution 1:[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.

Solution 2:[2]

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

Solution 3:[3]

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. I think there is a way to find the shortest number of routes without changing the route mark.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 machine_gun_lin
Solution 2 machine_gun_lin
Solution 3

Related Questions