Monday, 12 November 2012

Find shortest path in an array

0 comments

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;

Recent comments

Send Quick Massage

Name

Email *

Message *

Recent posts

Total Pageviews

Blog Archive