Check if a path exists from start to end cell in given Matrix with obstacles in at most K moves

Sample Test Cases

Input:
6 8
.##.##.. 
...###.# 
.#.#...# 
##...##. 
#..#.... 
..#####.
13
Output: Yes

Explanation: 

Path Length = 13

Path Length <= K, so the answer is Yes

Input:
6 8
.##.##.. 
...###.# 
.#.#...# 
##...##. 
#..#.... 
..#####.
11
Output: No

Approach

There are many ways to solve this problem, but we will discuss the simplest way.

Observation - To reach the bottom-right cell from the top-left cell, we have to move (N - 1) steps downward and (M - 1) steps in the right direction. As we can't move in the left or upward direction, the path length for all the paths from (0, 0) to (N - 1, M - 1) is always (N + M - 2).

So if there exists a path from top-left cell to bottom right cell and K >= N + M - 2, the answer is "Yes". Otherwise, the answer is "No".

Steps To Solve

• Make a function isValid(int x, int y, int &N, int &M, vector <string> &maze) to check whether the given cell (x, y) is valid or not.
  • If x >= N or y >= M, the current cell is out of bounds, so return false. There is no need to check for x < 0 and y < 0 because we can move only in the right or upward direction.
  • If (x, y) is a blocked cell(i.e., maze[x][y] == '#'), return false.
  • If all the above conditions are false, the cell is valid, return true.
• Make a function dfs(int r, int c, int &X, int &X, vector <string> & maize) that will check whether a path exists from the top-left corner of the maze to the bottom-right corner.
  • Base case: If the current cell (r, c) is the bottom-right cell, return true.
  • Mark the current cell (r, c) as visited by making it a blocked cell.
  • Check whether the cell (r, c + 1) is valid or not by calling the function isValid(r, c + 1, N, M) if it is a valid cell call the function dfs for (r + 1, c).
  • Similarly, check for cell (r + 1, c) and call the function dfs for it.
  • If we can reach the cell (N - 1, M - 1) from (r, c + 1) or (r, c + 1) (i.e., dfs(r + 1, c) == true or dfs(r, c + 1) == true) return true, otherwise return false.
• If K < N + M - 2 print "No", otherwise check whether there exists a path from (0, 0) to (N - 1, M - 1) by calling the function dfs(0, 0, N, M) if there is no such path print No otherwise print "Yes".

Code

#include <bits/stdc++.h>
using namespace std;
//function to check whether the given cell (x, y) is valid or not
bool isValid(int x, int y, int &N, int &M, vector <string> &maze){
   //out of bounds
   if(x >= N or y >= M)
       return false;
   //already visited or bloacked cell
   if(maze[x][y] == '#')
       return false;
   //valid cell
   return true;
}
bool dfs(int r, int c, int &N, int &M, vector <string> &maze){
   //Base Case
   if(r == N - 1 or c == M - 1)
       return true;
   //Mark the current cell visited
   maze[r][c] = '#';
   if(isValid(r + 1, c, N, M, maze)){
       //If we can reach the cell (N - 1, M - 1) from (r + 1, c)
       if(dfs(r + 1, c, N, M, maze))
           return true;
   }
   if(isValid(r, c + 1, N, M, maze)){
       //If we can reach the cell (N - 1, M - 1) from (r, c + 1)
       if(dfs(r, c + 1, N, M, maze))
           return true;
   }
   //we can't reach cell (N - 1, M - 1) from cell (r, c)
   return false;
}
signed main(){
   //rows, columns
   int N, M;
   cin >> N >> M;
   //input grid
   vector <string> maze(N);
   for(int i = 0; i < N; ++i){
       cin >> maze[i];
   }
   //maximum number of steps
   int K;
   cin >> K;
   if(K < N + M - 2 || !dfs(0, 0, N, M, maze))
       cout << "No" << "\n";
   else
       cout << "Yes" << "\n";
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Time Complexity

The time complexity is O(N * M)

Space Complexity

We are not using any extra space other than the input matrix, so the space complexity is O(1).
 

FAQs

1. What is DFS?
   DFS stands for depth-first search. It is a graph theory algorithm for recursively traversing or searching graphs and trees. 
    
2. What is the time complexity of DFS?
   The time complexity of DFS is O(V + E), where V is vertices and E is edges.
    
3. Can we solve the above problem using Dynamic Programming? 
   Yes, The above problem can also be solved using dynamic programming. If dp[i][j] represents the minimum number of moves to reach (N - 1, M - 1),then dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + 1.

Key Takeaways

In this article, we solved a graph theory problem. Having a good grasp of graph theory is very important for cracking coding interviews at MAANG. 

Check out this coding ninjas' blog on graph theory algorithms for getting a better hold on it.

Check out this problem - Root To Leaf Path

To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!

By Abhishek Ranjan