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

Live masterclass