Given a grid of size n*n filled with 0, 1, 2, 3. Check whether there is a path possible from the source to destination. You can traverse up, down, right and left.
The description of cells is as follows:
- A value of cell 1 means Source.
- A value of cell 2 means Destination.
- A value of cell 3 means Blank cell.
- A value of cell 0 means Wall. Note: There are only a single source and a single destination.
Example 1:
Input: grid = {{3,0,3,0,0},{3,0,0,0,3}
,{3,3,3,3,3},{0,2,3,0,0},{3,0,0,1,3}}
Output: 0
Explanation: The grid is-
3 0 3 0 0
3 0 0 0 3
3 3 3 3 3
0 2 3 0 0
3 0 0 1 3
There is no path to reach at (3,1) i,e at
destination from (4,3) i,e source.
Solution:
class Solution
{
//Function to find whether a path exists from the source to destination.
public boolean is_Possible(int[][] grid)
{
// Code here
for(int i =0;i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
if(grid[i][j]==1) {
return isDestinationPossible(grid,i,j);
}
}
}
return false;
}
public boolean isDestinationPossible(int[][] grid, int i, int j){
if(i<0 || i>=grid.length || j<0 || j>= grid[0].length ||
grid[i][j]==0 || grid[i][j] ==-1) return false;
if(grid[i][j] ==2) return true;
int temp = grid[i][j];
grid[i][j] = -1; //means this has been visited;
// up move
return isDestinationPossible(grid,i-1,j)||
// down move
isDestinationPossible(grid,i+1,j) ||
// left move
isDestinationPossible(grid,i,j-1) ||
// right move
isDestinationPossible(grid,i,j+1);
}
}
Top comments (0)