CODEWITHSUNDEEP
c++c
Jason
Jason

Reputation: 1613

Traveral maze and Depth First Search

I have learned DFS today and I tried practice tonight.

I encounter a problem in my program.

http://codepad.org/quq5FcwR

void dfs(int x,int y){
  if( maze[x][y]==0 ) maze[x][y]=2;
  if( maze[8][8]==2 ){
    flag=true;
    return;
  }
  if( maze[x+1][y]==0 && x+1<9 ){
    maze[x][y]=2;
    maze[x+1][y]=2;
    dfs(x+1,y);
    if(f lag==false ){
      maze[x+1][y]=0;
      maze[x][y]=0;
    }
  }
  else if( maze[x][y+1]==0 && y+1<9 ){
    maze[x][y]=2;
    maze[x][y+1]=2;
    dfs(x,y+1);                                
    if( flag==false ){
      maze[x][y+1]=0;
      maze[x][y]=0;
    }
  }
  else if( maze[x-1][y]==0 && x-1>0 ){
    maze[x][y]=2;
    maze[x-1][y]=2;
    dfs(x-1,y);                                
    if( flag==false ){
      maze[x-1][y]=0;
      maze[x][y]=0;
    }
  }
  else if( maze[x][y-1]==0 && y-1>0 ){
    maze[x][y]=2;
    maze[x][y-1]=2;
    dfs(x,y-1);                                
    if( flag==false ){
      maze[x][y-1]=0;
      maze[x][y]=0;
    }
  }
  return;
}

1. The link is the program that I write, but I don't know how to find the shortest path.

2. Can you give me some advice about how to do it with stack, I use only recursive.I have seen the wiki about it, but cannot still understand how to use the stack.(eg how to use 1-D array to record the point about 2-D array, I am so confused about it)

Thanks for you spend time reading my problems。

Upvotes: 1

Views: 2383

Answers (2)

Chakradar Raju
Chakradar Raju

Reputation: 2811

It is better to do a BFS for finding shortest path, than DFS.

You can use 2 1-D arrays to denote a point in 2-D maze.

I used to have xq[maxlength], yq[maxlength] as queue for traversing a 2-D maze.

when you want to insert a new position (xi,yi) into the queue do

xq[back] = xi;
yq[back] = yi;
back++;

when you want to get a point (xp,yp) from a queue,

xp = xq[front];
yp = yq[front];
front++;

Initially have front and back to be 0. Queue is done, and you can do a BFS using it.

Upvotes: 2

LiKao
LiKao

Reputation: 10658

There are multiple points to comment on in this case:

1) The simplest stack is the recursion stack, which you already seem to be using looking at your code. I.e. whenever you call dfs() from the function dfs() itself, all variables will be put onto the stack. In your case, when you call x and y will be saved for returning later. I.e. once you come back from dfs() x and y will have the same value they had before you called.

2) Before returning you have to undo the last change. In the beginning of your function you set maze[x][y]=2. Before you return you'll have to undo this, because this space might lead into a dead end.

3) DFS can be used to find any path with low memory usage. However the path found by DFS may not be the shortest one. There is another algorithm called BFS which will find the shortest path, but has a much higher memory usage. Then there is iterative DFS, which will find the shortest path, has low memory consumption, but takes more time. You'll have to decide what you want and then pick your algorithm.

Upvotes: 1

Related Questions