Saturday, September 8, 2012

Find shortest path in an array


Question:
Given a character array. Find if there exists a path from O to X. Here is an example
. . . . . . .
. . . . . . .
w . . . . . .
w .w.w..
. . . . O . .
. . w. . . .
. . . X . . .

You have to just keep in mind that you cannot go through 'W'.
Solution:
This can be solved by Simple Depth First Search using Recursion..
// 8 Adjacent points
int dx[]={+0,+0,+1,-1,+1,+1,-1,-1}; int dy[]={+1,-1,+0,+0,+1,-1,+1,-1};
bool visited[50][50]; string grid[50]; int m=50,n=50; bool dfs(int x,int y){ if(grid[x][y]=='X')return 1; bool res=0; visited[x][y]=1; for(int i=0;i<8;i++){ int newx=x+dx[i]; int newy=y+dy[i]; // Check whether the new point is valid one .. if(newx>=0 && newy>=0 && newx<m && newy<n){ // Check whether it is visited already / it is not 'W' if(visited[newx][newy]==0 && grid[x][y]!='W') res|=(dfs(newx,newy)); } } return res; } bool solve(){ int startx=0,starty=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]=='O'){ startx=i,starty=j; break; } } } return dfs(startx,starty); }
POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

No comments:

Post a Comment

Your feedback is always appreciated.
I will try to reply to your queries as soon as time allows.
Please do not spam Spam comments will be deleted immediately upon our review.