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

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

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:

• 8 Queens Problem Using Backtracking

Recommended Problems:

• Unique Paths
• Longest Path Directed Acyclic Graph
• Longest Path In A Tree
   

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!