-1

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?

H_Henry
  • 3
  • 4
  • 3
    No no no no NO! Don't use so-called "competition" sites to learn anything but really bad coding habits and often also invalid code. Invest in [some good C++ books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) and take computer science classes. Then after a few years, learning multiple languages and all the basic CS algorithms and data-structures, use such sites a kind of programmers crossword puzzles or brain-teasers. But until then don't even look at such a site. – Some programmer dude Apr 12 '22 at 10:23
  • 1
    On another note, "deep filtering search"? That seems like something completely different from depth first search. For future questions please take some time to read [the help pages](http://stackoverflow.com/help), take the SO [tour], read [ask], as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). And please try to get the acronyms correct. – Some programmer dude Apr 12 '22 at 10:57

3 Answers3

0

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.

machine_gun_lin
  • 16
  • 1
  • But for DFS, I've heard in some tutorials or websites that it can sort of **retreat** the ways not working and keep the ones working – H_Henry Apr 12 '22 at 11:11
  • Yes, it can, using exactly the trick I mentioned – machine_gun_lin Apr 12 '22 at 11:25
  • The char array you use is a global variable, and the coordinates that don't actually reach the end point (but are marked as visiteded in the vis array) have also been modified. – machine_gun_lin Apr 12 '22 at 11:27
0

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

machine_gun_lin
  • 16
  • 1
  • I just edited the post – H_Henry Apr 12 '22 at 11:35
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Apr 12 '22 at 12:01
0

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.

yn95ny
  • 1
  • 2
  • 2