DFS for maze traversal

I am just starting to learn graphs…I am trying to implement a question.This question is a common one-There is a maze and there are 2 ppl in the maze- Jack and Robot…the robot can move only in all directions except the diagonal wise…there are obstacles represented by ‘|’… ’ . ’ represent a path…we have to find out whether robot can reach jack or not?
I tried to implement this one…but i think there is some-problem with my recursive function

here is my code…

1 Like

Mistakes that you are making:

1. if(ch[i][j]==‘R’) x=i,y=j; break;
No braces after if// Will break as soon as the control reaches the INNER LOOP, so x and y will contain -1,-1 for some test cases (Results in RTE).

2. There is no boundary check while you call dfs function recursively // Results in RTE

Corrected code :https://ideone.com/DwtCRX

2 Likes

Thanks a lot dude…:slight_smile:
I am just a newbie…by the way should we visit every node? i mean in the corrected code we are even visiting the node which is a block…should we visit the blocked node also?

No , You need not do that! Put this check: if(ch[x][y]==’|’) return;
as soon as the dfs function starts … ie; before marking visited[x][y] = true…! Check the corrected code link again …

2 Likes

Thanks bro!!

1 Like