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<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

  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