Find whether path exist || GRAPHS || @ APPROACHES
Vidhu
93

Question:
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.
Eg

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.

Similar to find no of islands (see my blog here for this)
ALways prefer dfs for source to destination path problems

DFS

 void dfs(int i, int j, int n, vector < vector < bool >> & visited, vector < vector < int >> & grid) {
     
    if (i < 0 || j < 0 || i >= n || j >= n || visited[i][j] == true || grid[i][j] == 0) return;
   
    visited[i][j] = true;
    dfs(i + 1, j, n, visited, grid);
    dfs(i, j + 1, n, visited, grid);
    dfs(i - 1, j, n, visited, grid);
    dfs(i, j - 1, n, visited, grid);
 }
 
 bool is_Possible(vector < vector < int >> & grid) {
   int n = grid.size();
   int destination_ROW, destination_COL;
   vector < vector < bool >> visited(n, vector < bool > (n, false));
   for (int i = 0; i < n; i++) {
     for (int j = 0; j < n; j++) {
       if (grid[i][j] == 1 && visited[i][j] == false)
         dfs(i, j, n, visited, grid);
       if (grid[i][j] == 2) {
         destination_ROW = i;
         destination_COL = j;
       }
     }
   }
   return visited[destination_ROW][destination_COL];
 }

BFS

   vector<int>dx = {-1,0,1,0};
    vector<int>dy = {0,-1,0,1};  

    bool isValid(int x, int y, int n, int m){
        return (x >= 0 and x < n and y >=0 and y < m);
    }
    
    //Function to find whether a path exists from the source to destination. 
    bool is_Possible(vector<vector<int>>& grid) 
    {
        int n = grid.size();
        int m = grid[0].size();  // here m=n

        queue<pair<int, int>>q;

        for(int i = 0; i < n; i++)
        {
        	for(int j = 0; j < m; j++)
        	{
        		if(grid[i][j] == 1){
        			q.push({i,j});
        		}
        	}
        }
        
        while(!q.empty())
        {
        	int x = q.front().first;
        	int y = q.front().second;
        	q.pop();
        	for(int i = 0; i < 4; i++)
        	{
        		int n_x = x + dx[i];
        		int n_y = y + dy[i];
        		
        		if(isValid(n_x, n_y, n, m))
        		{
        			if(grid[n_x][n_y] == 2)
        				return true;
 
        			if(grid[n_x][n_y] == 3){
        				grid[n_x][n_y] = 1;
        				q.push({n_x, n_y});
        			}
        		}
        	}
        }
        return false;

    }
Comments (0)