1.
Problem Statement
2.
Constraints
3.
Sample Test Cases
4.
Approach
5.
Code
6.
Dry Run
7.
Time Complexity
8.
Space Complexity
9.
FAQs
10.
Key Takeaways
Last Updated: Mar 27, 2024
Hard

# Print All Paths from a Source Point to All the 4 Corners of a Matrix

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Problem Statement

Given a 2D matrix of M rows and N columns consisting of characters '.' and '#'. '#' represents the blocked cell, and '.' represents the empty cell. Print all the paths possible paths to reach any of the four corner cells of the maze (0, 0), (0, N - 1), (0, M - 1), and (N - 1, M - 1), starting from the given cell (X, Y).

## Constraints

1 <= N, M <= 1000

0 <= X <= N - 1

0 <= Y <= M - 1

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
.##.##..
...###.#
.#.#...#
##...##.
#..#....
..#####.
4 2

Output:
UUULLU
URRURRUUR
URRDRRRD
LDL``````

Explanation :

Also see, Euclid GCD Algorithm

## Approach

We can solve this problem using recursion and backtracking. The idea is to start from the given cell and recursively iterate to the valid adjacent cells. We can use a vector or string to store the current path, and if a path is a valid path(i.e., we reached any of the four corners), we will store that path.

Steps To Solve

• Make a function isValid(int x, int y, int &N, int &M, vector <vector<bool>> &vis, vector <string> &maze) to check whether the given cell (x, y) is valid or not.
• If x < 0 or y < 0 or x > N or y > M then the current cell is out of bounds so return false.
• If (x, y) is a blocked cell(i.e., maze[x][y] == '#'), return false
• If vis[x][y] == true, then the cell (x, y) is already visited hence it is invalid so return false.
• If all the above conditions are false, the cell is valid, so return true.
• Make a function checkDest(int x, int y, int &N, int &M) to check whether the given cell (x, y) is one of the four corners or not.
• If (x, y) is equal to one of the four corners (0, 0), (0, N - 1), (0, M - 1) or (N - 1, M - 1) return true otherwise return false.
• Make a function 'print_paths(int x, int y, int &N, int &M, string &curr, vector <string> &maze, vector <vector<bool>> &vis, vector <string>&validPaths)' to find all the valid path from the given cell to any of the four corner. (x, y) denotes the current cell, string curr stores the current path, vector maze stores the input grid, 2D boolean matrix vis is used to mark all the visited cells, and a vector of string validPaths is used to store all the valid paths.
• Base case: Check if the current cell is one of the four corners or not by calling the function 'checkDest(x, y, N, M)'. If it returns true, store the current path in the vector validPaths.
• Iterate the direction vectors dx[] and dy[] simultaneously to generate the coordinate (newX, newY) of all the adjacent cells.
•  If it is a valid cell, then mark it visited and push the direction (U', 'D', 'L' or 'R') corresponding to the direction vector to the string curr, then recursively call the function paths(newX, newY, N, M, curr, maze, vis, validPaths).
• Backtrack to explore other paths.
• Mark the given cell (X, Y) as visited and initiate the function paths from (X, Y)

## Code

``````#include <bits/stdc++.h>
using namespace std;
const int M = 1e2 + 7;
//direction vector
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
//direction corresponding to each direction vector
char dir[] = {'U', 'D', 'L', 'R'};
//function to check whether the given cell (x, y) is valid or not.
bool isValid(int x, int y, int &N, int &M, vector <vector<bool>> &vis, vector <string> &maze){
//the current cell is out of bounds so return false.
if(x < 0 || y < 0 || x >= N || y >= M)
return false;
//If the cell (x, y) is already visited, return false
if(vis[x][y])
return false;
//If (x, y) is a blocked cell, return false
if(maze[x][y] == '#')
return false;
//valid cell
return true;
}
//function to check whether the given cell (x, y) is one of the four corners or not
bool checkDest(int x, int y, int &N, int &M){
if((x == N - 1 and y == M - 1) or (x == 0 and y == 0)
or (x == N - 1 and y == 0) or (x == 0 and y == M - 1))
return true;
return false;
}
//function to find all the valid path from the given cell to any of the four corner.
void paths(int x, int y, int &N, int &M, string &curr,
vector <string> &maze,
vector <vector<bool>> &vis,
vector <string> &validPaths){
cout << x << " " << y << "\n";
//Base case: Check if the current cell is one of the four corners or not
//If it is, then store the current path in the vector validPaths
if(checkDest(x, y, N, M)){
validPaths.push_back(curr);
return;
}
//Iterate the direction vectors dx[] and dy[]
//simultaneously to generate the coordinate (newX, newY) of all the adjacent cells
for(int i = 0; i < 4; ++i){

int newX = x + dx[i];
int newY = y + dy[i];

//direction - L, U, D, or R
char direction = dir[i];
//check the new cell is valid or not
if(isValid(newX, newY, N, M, vis, maze)){
//mark the cell as visited
vis[newX][newY] = true;
//store the direction
curr.push_back(direction);
//recursive call
paths(newX, newY, N, M, curr, maze, vis, validPaths);
//Backtrack to explore other paths
curr.pop_back();
vis[newX][newY] = false;
}
}
}
signed main(){
//rows, coloumns
int N, M;
cin >> N >> M;
//Given grid
vector <string> maze(N);
for(int i = 0; i < N; i++){
cin >> maze[i];
}
//given cell
int X, Y;
cin >> X >> Y;
//2D boolean matrix vis to mark all the visited cells
vector <vector<bool>> vis(N, vector <bool> (M, 0));
//used to store all the valid paths
vector <string> validPaths;
string curr = "";
//Mark the given cell (X, Y) as visited
vis[X][Y] = true;
//initiate the function paths from (X, Y)
paths(X, Y, N, M, curr, maze, vis, validPaths);
//Print all the valid paths
for(auto u : validPaths)
cout << u << "\n";
return 0;
}``````

## Time Complexity

The time complexity is O(3^(N * M))

## Space Complexity

The space complexity is O(3^(N * M)

## FAQs

1. What is Backtracking?
Backtracking is an algorithmic tool that recursively generates all the possible combinations to solve the given problem.

## Key Takeaways

In this article, we solved a problem using recursion and backtracking. If you want to master competitive programming or prepare for coding interviews, then backtracking is one of the most important topics. Check out this coding ninjas' blog for getting a better hold on it.

Related Article:

Recommended Problems:

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!

Live masterclass