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 bottomright cell from the topleft 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 topleft 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 topleft corner of the maze to the bottomright corner.
 Base case: If the current cell (r, c) is the bottomright 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

What is DFS?
DFS stands for depthfirst search. It is a graph theory algorithm for recursively traversing or searching graphs and trees.

What is the time complexity of DFS?
The time complexity of DFS is O(V + E), where V is vertices and E is edges.

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 onestop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various productbased companies by providing Online Mock Test Series and many more benefits.
Happy learning!
By Abhishek Ranjan