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){
//coordinates of the adjacent cell
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;
}
Dry Run
Time Complexity
The time complexity is O(3^(N * M))
Space Complexity
The space complexity is O(3^(N * M)
FAQs

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