Given a positive integer K and a matrix grid of dimensions N * M consisting of characters ‘.’ and ‘#’, where ‘.’ represents the unblocked cells and ‘#’ represents the blocked cells, the task is to check if the bottom-right of the grid can be reached from the top-left cell of the matrix through unblocked cells in at most K moves or not such that it takes one move to move to its adjacent cell in the right or downward direction.
Examples:
Input: grid[][] = {{‘.’, ‘.’, ‘.’}, {‘#’, ‘.’, ‘.’}, {‘#’, ‘#’, ‘.’}}, K = 4
Output: Yes
Explanation: It is possible to reach the bottom right cell of the given grid using the following set of moves: right-> down -> right -> down. Hence, the number of moves required are 4 which is the minimum possible and is less than K.Input: grid[][] = {{‘.’, ‘.’, ‘.’, ‘.’}, {‘.’, ‘.’, ‘.’, ‘.’}, {‘#’, ‘#’, ‘#’, ‘#’}, {‘.’, ‘.’, ‘.’, ‘.’}}, K = 4
Output: No
Explanation: There are no possible set of moves to reach the bottom right cell from the top left cell of the given matrix.
Approach: The given problem can be solved with the help of Dynamic Programming by using a tabulation approach. It can be solved by precomputing the minimum number of moves required to move from the top-left to the bottom-right cell using an approach similar to the one discussed in this article. It can be observed that if dp[i][j] represents the minimum number of moves to reach the cell (i, j) from (0, 0), then the DP relation can be formulated as below:
dp[i][j] = min(dp[i][j], 1 + dp[i – 1][j], 1+ dp[i][j – 1]))
Thereafter, if the minimum number of moves is at most K then print “Yes”, otherwise print “No”.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include "bits/stdc++.h"using namespace std;// Function to check if it is possible// to reach the bottom right of the grid// from top left using atmost K movesstring canReach(vector<vector<char> >& grid, int K){ int N = grid.size(); int M = grid[0].size(); // Stores the DP states vector<vector<long long> > dp( N, vector<long long>(M, INT_MAX)); // if first cell or last cell is blocked then // not possible if(grid[0][0] != '.' || grid[N - 1][M - 1] != '.') return "No"; // Initial condition dp[0][0] = 0; // Initializing the DP table // in 1st row for (int i = 1; i < M; i++) { if (grid[0][i] == '.') { dp[0][i] = 1 + dp[0][i - 1]; } else break; } // Initializing the DP table // in 1st column for (int i = 1; i < N; i++) { if (grid[i][0] == '.') { dp[i][0] = 1 + dp[i - 1][0]; } else break; } // Iterate through the grid for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { // If current position // is not an obstacle, // update the dp state if (grid[i][j] == '.') { dp[i][j] = min( dp[i][j], 1 + min(dp[i - 1][j], dp[i][j - 1])); } } } // Return answer return (dp[N - 1][M - 1] <= K ? "Yes" : "No");}// Driver Codeint main(){ vector<vector<char> > grid = { { '.', '.', '.' }, { '#', '.', '.' }, { '#', '#', '.' } }; int K = 4; cout << canReach(grid, K); return 0;} |
Java
// Java implementation for the above approach//include "bits/stdJava.h"import java.util.*;class GFG{// Function to check if it is possible// to reach the bottom right of the grid// from top left using atmost K movesstatic String canReach(char[][] grid, int K){ int N = grid.length; int M = grid[0].length; // Stores the DP states int[][] dp = new int[N][M]; for(int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { dp[i][j] = Integer.MAX_VALUE; } } // if first cell or last cell is blocked then // not possible if(grid[0][0] != '.' || grid[N - 1][M - 1] != '.') return "No"; // Initial condition dp[0][0] = 0; // Initializing the DP table // in 1st row for (int i = 1; i < M; i++) { if (grid[0][i] == '.') { dp[0][i] = 1 + dp[0][i - 1]; } else break; } // Initializing the DP table // in 1st column for (int i = 1; i < N; i++) { if (grid[i][0] == '.') { dp[i][0] = 1 + dp[i - 1][0]; } else break; } // Iterate through the grid for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { // If current position // is not an obstacle, // update the dp state if (grid[i][j] == '.') { dp[i][j] = Math.min( dp[i][j], 1 + Math.min(dp[i - 1][j], dp[i][j - 1])); } } } // Return answer return (dp[N - 1][M - 1] <= K ? "Yes" : "No");}// Driver Codepublic static void main(String[] args){ char[][] grid = { { '.', '.', '.' }, { '#', '.', '.' }, { '#', '#', '.' } }; int K = 4; System.out.print(canReach(grid, K));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation for the above approachINT_MAX = 2147483647# Function to check if it is possible# to reach the bottom right of the grid# from top left using atmost K movesdef canReach(grid, K): N = len(grid) M = len(grid[0]) # Stores the DP states dp = [[INT_MAX for _ in range(M)] for _ in range(N)] # if first cell or last cell is blocked then # not possible if(grid[0][0] != '.' or grid[N - 1][M - 1] != '.'): return("No") # Initial condition dp[0][0] = 0 # Initializing the DP table # in 1st row for i in range(1, M): if (grid[0][i] == '.'): dp[0][i] = 1 + dp[0][i - 1] else: break # Initializing the DP table # in 1st column for i in range(1, N): if (grid[i][0] == '.'): dp[i][0] = 1 + dp[i - 1][0] else: break # Iterate through the grid for i in range(1, N): for j in range(1, M): # If current position # is not an obstacle, # update the dp state if (grid[i][j] == '.'): dp[i][j] = min(dp[i][j], 1 + min(dp[i - 1][j], dp[i][j - 1])) # Return answer if dp[N - 1][M - 1] <= K: return("Yes") else: return("No")# Driver Codeif __name__ == "__main__": grid = [ [ '.', '.', '.' ], [ '#', '.', '.' ], [ '#', '#', '.' ] ] K = 4 print(canReach(grid, K))# This code is contributed by rakeshsahni |
C#
// C# implementation for the above approach//include "bits/stdJava.h"using System;class GFG{// Function to check if it is possible// to reach the bottom right of the grid// from top left using atmost K movesstatic String canReach(char[,] grid, int K){ int N = grid.GetLength(0); int M = grid.GetLength(1); // Stores the DP states int[,] dp = new int[N,M]; for(int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { dp[i, j] = int.MaxValue; } } // if first cell or last cell is blocked then // not possible if(grid[0, 0] != '.' || grid[N - 1, M - 1] != '.') return "No"; // Initial condition dp[0, 0] = 0; // Initializing the DP table // in 1st row for (int i = 1; i < M; i++) { if (grid[0, i] == '.') { dp[0, i] = 1 + dp[0, i - 1]; } else break; } // Initializing the DP table // in 1st column for (int i = 1; i < N; i++) { if (grid[i, 0] == '.') { dp[i, 0] = 1 + dp[i - 1, 0]; } else break; } // Iterate through the grid for (int i = 1; i < N; i++) { for (int j = 1; j < M; j++) { // If current position // is not an obstacle, // update the dp state if (grid[i, j] == '.') { dp[i, j] = Math.Min( dp[i, j], 1 + Math.Min(dp[i - 1, j], dp[i, j - 1])); } } } // Return answer return (dp[N - 1, M - 1] <= K ? "Yes" : "No");}// Driver Codepublic static void Main(){ char[,] grid = { { '.', '.', '.' }, { '/', '.', '.' }, { '/', '/', '.' } }; int K = 4; Console.Write(canReach(grid, K));}}// This code is contributed by Saurabh jaiswal |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to check if it is possible // to reach the bottom right of the grid // from top left using atmost K moves function canReach(grid, K) { let N = grid.length; let M = grid[0].length; // Stores the DP states let dp = new Array(N); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(M).fill(Number.MAX_VALUE); } // if first cell or last cell is blocked then // not possible if(grid[0][0] != '.' || grid[N - 1][M - 1] != '.') return "No"; // Initial condition dp[0][0] = 0; // Initializing the DP table // in 1st row for (let i = 1; i < M; i++) { if (grid[0][i] == '.') { dp[0][i] = 1 + dp[0][i - 1]; } else break; } // Initializing the DP table // in 1st column for (let i = 1; i < N; i++) { if (grid[i][0] == '.') { dp[i][0] = 1 + dp[i - 1][0]; } else break; } // Iterate through the grid for (let i = 1; i < N; i++) { for (let j = 1; j < M; j++) { // If current position // is not an obstacle, // update the dp state if (grid[i][j] == '.') { dp[i][j] = Math.min( dp[i][j], 1 + Math.min(dp[i - 1][j], dp[i][j - 1])); } } } // Return answer return (dp[N - 1][M - 1] <= K ? "Yes" : "No"); } // Driver Code let grid = [['.', '.', '.'], ['#', '.', '.'], ['#', '#', '.']]; let K = 4; document.write(canReach(grid, K)); // This code is contributed by Potta Lokesh </script> |
Yes
Time Complexity: O(N*M), as we are using nested loops to traverse N*M times.
Auxiliary Space: O(N*M), as we are using extra space for dp matrix.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
