DEV Community

Prashant Mishra
Prashant Mishra

Posted on • Originally published at practice.geeksforgeeks.org

Find Weather Path Exists GeeksForGeeks

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:

  1. A value of cell 1 means Source.
  2. A value of cell 2 means Destination.
  3. A value of cell 3 means Blank cell.
  4. 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.
Enter fullscreen mode Exit fullscreen mode

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

    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)