Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Statement
2.
Constraints
3.
Sample Test Cases
4.
Approach
5.
Code
6.
Time Complexity
7.
Space Complexity
8.
FAQs
9.
Key Takeaways
Last Updated: Mar 27, 2024

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

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Problem Statement

You are given a 2D matrix of M rows and N columns consisting of characters '.' and '#'. '#' represents the blocked cell, and '.' represents the empty cell. Check if a path exists from the top-left corner to the bottom-right corner in the given matrix in at most K moves.

 

Constraints

1 <= N, M <= 1000

1 <= K <= 10^6

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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

Previous article
Count of valid arrays of size P with elements in the range [1, N] having duplicates at least M distance apart
Next article
Longest subsequence such that the difference between adjacent elements is K
Live masterclass