Given a grid of n rows and m columns. Currently, you are at point (0, 0) and must reach point (n-1, m-1). If any cell contains 0, it is a free cell, if it contains 1, there is an obstacle and you can’t pass through the cell, and if it contains 2, that means it is free and if you step into this cell, you can pass through any adjacent cell of it that contains obstacles. In one step you can go one unit in any four directions (Inside the grid), the task is to find the minimum number of steps to reach the destination if it is impossible return -1.
Examples:
Input: n = 2, m = 3, grid[][] = {{0, 2, 1}, {0, 1, 0}}
Output: 3
Explanation: You can reach (0, 1) cell in one step, then you can pass through the blocked cell (0,2) and reach (1, 2) in 3 steps.Input: n = 2, m = 3, grid = {{0, 0, 1}, {0, 1, 0}}
Output: -1
Explanation: You can’t reach your destination.
Finding minimum steps using BFS (Breadth-First Search)
The idea is to use Breadth-First Search (BFS) to find the minimum number of steps required to reach the destination. The BFS algorithm helps explore all possible paths from the starting point (0,0) to the destination point (n-1, m-1).
Follow the steps to solve the problem:
- First, check whether the starting point (0, 0) or the destination point (n-1, m-1) is blocked (value 1). If either of them is blocked, it means that not able to reach the destination.
- Use two arrays,
dx
anddy
, to represent the four possible directions (up, right, down, and left). - Use a queue to perform BFS traversal on the grid.
- Also, use a 2D vector
dis
to keep track of the minimum number of steps required to reach. initialize all values to -1 to indicate that they are not yet visited. - During BFS traversal, process each cell in the queue one by one. For each cell, explore its four neighboring cells using
dx
anddy
.- If the neighboring cell is within the grid bounds, and it is either a free cell (value 0) or a special cell (value 2), proceed to process it.
- If the neighboring cell is a special cell (value 2), update the grid to mark the adjacent blocked cells as free (value 0). This allows us to bypass obstacles by stepping into the special cell.
- Then continue the BFS traversal from the neighboring cell and keep updating the minimum steps needed to reach each cell in the
dis
array. - Finally, look at the value in the “dis” vector for the bottom-right cell (n-1, m-1). This is the shortest way to find it. If it is still -1, it means there is no way at all.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int possiblePath( int n, int m, vector<vector< int > >& grid) { // Check if the source or destination // cell is blocked if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) { // Return -1 to indicate no path return -1; } // Create a queue to store the // cells to explore queue<pair< int , int > > q; // Add the source cell to the queue // and mark its distance as 0 q.push({ 0, 0 }); // Define two arrays to represent the // four directions of movement int dx[4] = { -1, 0, 1, 0 }; int dy[4] = { 0, 1, 0, -1 }; // Create a 2D vector to store the // distance of each cell // from the source vector<vector< int > > dis(n, vector< int >(m, -1)); // Set the distance of the source // cell as 0 dis[0][0] = 0; // Loop until the queue is empty or // the destination is reached while (!q.empty()) { // Get the front cell from the // queue and remove it pair< int , int > p = q.front(); q.pop(); // Loop through the four directions // of movement for ( int i = 0; i < 4; i++) { // Calculate the coordinates // of the neighboring cell int x = p.first + dx[i]; int y = p.second + dy[i]; // Check if the neighboring // cell is inside the grid // and not visited before if (x >= 0 && x < n && y >= 0 && y < m && dis[x][y] == -1) { // Check if the neighboring // cell is free or special if (grid[x][y] == 0 || grid[x][y] == 2) { // Set the distance of the // neighboring cell as one // more than the current cell dis[x][y] = dis[p.first][p.second] + 1; // Add the neighboring cell // to the queue for // further exploration q.push({ x, y }); } // Check if the neighboring // cell is special if (grid[x][y] == 2) { // Loop through the four // directions of movement again for ( int j = 0; j < 4; j++) { // Calculate the coordinates // of the adjacent cell int xx = x + dx[j]; int yy = y + dy[j]; // Check if the adjacent // cell is inside the grid if (xx >= 0 && xx < n && yy >= 0 && yy < m) { // Check if the adjacent // cell is blocked if (grid[xx][yy] == 1) { // Change the adjacent // cell to free grid[xx][yy] = 0; } } } } } } } // Return the distance of the // destination cell from the source return dis[n - 1][m - 1]; } // Drivers code int main() { int n = 3; int m = 4; vector<vector< int > > grid = { { 0, 1, 2, 1 }, { 2, 1, 0, 0 }, { 0, 2, 1, 0 } }; int result = possiblePath(n, m, grid); // Function Call cout << "Output: " << result << endl; return 0; } |
Java
// Java code for the above approach: import java.util.*; public class Main { public static int possiblePath( int n, int m, int [][] grid) { // Check if the source or destination cell is blocked if (grid[ 0 ][ 0 ] == 1 || grid[n - 1 ][m - 1 ] == 1 ) { // Return -1 to indicate no path return - 1 ; } // Create a queue to store the cells to explore Queue< int []> q = new LinkedList<>(); // Add the source cell to the queue and mark its distance as 0 q.add( new int []{ 0 , 0 }); // Define two arrays to represent the four directions of movement int [] dx = {- 1 , 0 , 1 , 0 }; int [] dy = { 0 , 1 , 0 , - 1 }; // Create a 2D array to store the distance of each cell // from the source int [][] dis = new int [n][m]; for ( int i = 0 ; i < n; i++) { Arrays.fill(dis[i], - 1 ); } // Set the distance of the source cell as 0 dis[ 0 ][ 0 ] = 0 ; // Loop until the queue is empty or the destination is reached while (!q.isEmpty()) { // Get the front cell from the queue and remove it int [] p = q.poll(); int x = p[ 0 ]; int y = p[ 1 ]; // Loop through the four directions of movement for ( int i = 0 ; i < 4 ; i++) { // Calculate the coordinates of the neighboring cell int xx = x + dx[i]; int yy = y + dy[i]; // Check if the neighboring cell is inside the grid // and not visited before if (xx >= 0 && xx < n && yy >= 0 && yy < m && dis[xx][yy] == - 1 ) { // Check if the neighboring cell is free or special if (grid[xx][yy] == 0 || grid[xx][yy] == 2 ) { // Set the distance of the neighboring cell as one // more than the current cell dis[xx][yy] = dis[x][y] + 1 ; // Add the neighboring cell to the queue for // further exploration q.add( new int []{xx, yy}); } // Check if the neighboring cell is special if (grid[xx][yy] == 2 ) { // Loop through the four directions of movement again for ( int j = 0 ; j < 4 ; j++) { // Calculate the coordinates of the adjacent cell int xxx = xx + dx[j]; int yyy = yy + dy[j]; // Check if the adjacent cell is inside the grid if (xxx >= 0 && xxx < n && yyy >= 0 && yyy < m) { // Check if the adjacent cell is blocked if (grid[xxx][yyy] == 1 ) { // Change the adjacent cell to free grid[xxx][yyy] = 0 ; } } } } } } } // Return the distance of the destination cell from the source return dis[n - 1 ][m - 1 ]; } public static void main(String[] args) { int n = 3 ; int m = 4 ; int [][] grid = { { 0 , 1 , 2 , 1 }, { 2 , 1 , 0 , 0 }, { 0 , 2 , 1 , 0 } }; int result = possiblePath(n, m, grid); // Function Call System.out.println( "Output: " + result); } } |
Python
from collections import deque def possiblePath(n, m, grid): # Check if the source or destination cell is blocked if grid[ 0 ][ 0 ] = = 1 or grid[n - 1 ][m - 1 ] = = 1 : # Return -1 to indicate no path return - 1 # Create a queue to store the cells to explore q = deque() # Add the source cell to the queue and mark its distance as 0 q.append(( 0 , 0 )) # Define two arrays to represent the four directions of movement dx = [ - 1 , 0 , 1 , 0 ] dy = [ 0 , 1 , 0 , - 1 ] # Create a 2D list to store the distance of each cell from the source dis = [[ - 1 for _ in range (m)] for _ in range (n)] # Set the distance of the source cell as 0 dis[ 0 ][ 0 ] = 0 # Loop until the queue is empty or the destination is reached while q: # Get the front cell from the queue and remove it p = q.popleft() # Loop through the four directions of movement for i in range ( 4 ): # Calculate the coordinates of the neighboring cell x = p[ 0 ] + dx[i] y = p[ 1 ] + dy[i] # Check if the neighboring cell is inside the grid and not visited before if 0 < = x < n and 0 < = y < m and dis[x][y] = = - 1 : # Check if the neighboring cell is free or special if grid[x][y] = = 0 or grid[x][y] = = 2 : # Set the distance of the neighboring cell as one more than the current cell dis[x][y] = dis[p[ 0 ]][p[ 1 ]] + 1 # Add the neighboring cell to the queue for further exploration q.append((x, y)) # Check if the neighboring cell is special if grid[x][y] = = 2 : # Loop through the four directions of movement again for j in range ( 4 ): # Calculate the coordinates of the adjacent cell xx = x + dx[j] yy = y + dy[j] # Check if the adjacent cell is inside the grid if 0 < = xx < n and 0 < = yy < m: # Check if the adjacent cell is blocked if grid[xx][yy] = = 1 : # Change the adjacent cell to free grid[xx][yy] = 0 # Return the distance of the destination cell from the source return dis[n - 1 ][m - 1 ] # Driver code if __name__ = = "__main__" : n = 3 m = 4 grid = [ [ 0 , 1 , 2 , 1 ], [ 2 , 1 , 0 , 0 ], [ 0 , 2 , 1 , 0 ] ] result = possiblePath(n, m, grid) # Function Call print (result) |
C#
// C# implementation of the above approach using System; using System.Collections.Generic; public class MainClass { public static int PossiblePath( int n, int m, int [][] grid) { // Check if the source or destination cell is blocked if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) { // Return -1 to indicate no path return -1; } // Create a queue to store the cells to explore Queue< int []> q = new Queue< int []>(); // Add the source cell to the queue and mark its distance as 0 q.Enqueue( new int [] { 0, 0 }); // Define two arrays to represent the four directions of movement int [] dx = { -1, 0, 1, 0 }; int [] dy = { 0, 1, 0, -1 }; // Create a 2D array to store the distance of each cell // from the source int [][] dis = new int [n][]; for ( int i = 0; i < n; i++) { dis[i] = new int [m]; for ( int j = 0; j < m; j++) { dis[i][j] = -1; } } // Set the distance of the source cell as 0 dis[0][0] = 0; // Loop until the queue is empty or the destination is reached while (q.Count > 0) { // Get the front cell from the queue and remove it int [] p = q.Dequeue(); int x = p[0]; int y = p[1]; // Loop through the four directions of movement for ( int i = 0; i < 4; i++) { // Calculate the coordinates of the neighboring cell int xx = x + dx[i]; int yy = y + dy[i]; // Check if the neighboring cell is inside the grid // and not visited before if (xx >= 0 && xx < n && yy >= 0 && yy < m && dis[xx][yy] == -1) { // Check if the neighboring cell is free or special if (grid[xx][yy] == 0 || grid[xx][yy] == 2) { // Set the distance of the neighboring cell as one // more than the current cell dis[xx][yy] = dis[x][y] + 1; // Add the neighboring cell to the queue for // further exploration q.Enqueue( new int [] { xx, yy }); } // Check if the neighboring cell is special if (grid[xx][yy] == 2) { // Loop through the four directions of movement again for ( int j = 0; j < 4; j++) { // Calculate the coordinates of the adjacent cell int xxx = xx + dx[j]; int yyy = yy + dy[j]; // Check if the adjacent cell is inside the grid if (xxx >= 0 && xxx < n && yyy >= 0 && yyy < m) { // Check if the adjacent cell is blocked if (grid[xxx][yyy] == 1) { // Change the adjacent cell to free grid[xxx][yyy] = 0; } } } } } } } // Return the distance of the destination cell from the source return dis[n - 1][m - 1]; } public static void Main( string [] args) { int n = 3; int m = 4; int [][] grid = new int [][] { new int [] { 0, 1, 2, 1 }, new int [] { 2, 1, 0, 0 }, new int [] { 0, 2, 1, 0 } }; int result = PossiblePath(n, m, grid); // Function Call Console.WriteLine( "Output: " + result); } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
function GFG(n, m, grid) { // Check if the source or destination cell is blocked if (grid[0][0] === 1 || grid[n - 1][m - 1] === 1) { // Return -1 to indicate no path return -1; } // Create a queue to store the cells to explore const queue = []; queue.push([0, 0]); // Define two arrays to represent // the four directions of movement const dx = [-1, 0, 1, 0]; const dy = [0, 1, 0, -1]; const dis = new Array(n); for (let i = 0; i < n; i++) { dis[i] = new Array(m).fill(-1); } // Set the distance of the source cell as 0 dis[0][0] = 0; // Loop until the queue is empty or // the destination is reached while (queue.length > 0) { // Get the front cell from the queue and remove it const p = queue.shift(); const x = p[0]; const y = p[1]; // Loop through the four directions of movement for (let i = 0; i < 4; i++) { // Calculate the coordinates of the neighboring cell const xx = x + dx[i]; const yy = y + dy[i]; if (xx >= 0 && xx < n && yy >= 0 && yy < m && dis[xx][yy] === -1) { // Check if the neighboring cell is free or special if (grid[xx][yy] === 0 || grid[xx][yy] === 2) { dis[xx][yy] = dis[x][y] + 1; // Add the neighboring cell to the queue for further exploration queue.push([xx, yy]); } // Check if the neighboring cell is special if (grid[xx][yy] === 2) { for (let j = 0; j < 4; j++) { // Calculate the coordinates of the adjacent cell const xxx = xx + dx[j]; const yyy = yy + dy[j]; // Check if the adjacent cell is inside the grid if (xxx >= 0 && xxx < n && yyy >= 0 && yyy < m) { // Check if the adjacent cell is blocked if (grid[xxx][yyy] === 1) { // Change the adjacent cell to free grid[xxx][yyy] = 0; } } } } } } } // Return the distance of the destination cell // from the source return dis[n - 1][m - 1]; } // Driver code const n = 3; const m = 4; const grid = [ [0, 1, 2, 1], [2, 1, 0, 0], [0, 2, 1, 0] ]; const result = GFG(n, m, grid); // Function Call console.log( "Output: " + result); |
Output: 5
Time complexity: O(N * M)
Auxiliary Space: O(N * M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!