## Find shortest path in an array

 Tweet 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
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..
```

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

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

Name

Email *

Message *