Monday 12 November 2012

Find shortest path in an array

  Adjust the font size     Reset ↕

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

Click Here To add 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.

Blogger Widgets

Recent comments

Send Quick Massage

Name

Email *

Message *

Recent posts

Total Pageviews

Blog Archive