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

Q: What are the four corners of a matrix?

The four corners of a matrix are the cells located at: Top-left: (0, 0) Top-right: (0, n - 1) Bottom-left: (m - 1, 0) Bottom-right: (m - 1, n - 1) Here, m is the number of rows and n is the number of columns. These corners are considered as destinations when finding paths from a given source point.

Introduction

In many algorithmic challenges, navigating through a matrix isn’t just about finding a single path—it’s about exploring all possible paths to specific destinations. One such interesting problem is determining all the unique paths from a given source point to each of the four corners of a matrix.

This type of problem blends concepts from recursion, backtracking, and matrix traversal, making it an excellent exercise for improving problem-solving skills in grid-based environments. It's especially useful for understanding movement constraints, handling edge conditions, and optimizing recursive solutions. In this blog, we'll discuss how to approach and solve this problem, step by step.

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

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

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

C++
Java
Python

C++

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

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.*;

public class MatrixPaths {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static char[] dir = {'U', 'D', 'L', 'R'};

    static boolean isValid(int x, int y, int N, int M, boolean[][] vis, String[] maze) {
        if (x < 0 || y < 0 || x >= N || y >= M) return false;
        if (vis[x][y]) return false;
        if (maze[x].charAt(y) == '#') return false;
        return true;
    }

    static boolean checkDest(int x, int y, int N, int M) {
        return (x == N - 1 && y == M - 1) ||
               (x == 0 && y == 0) ||
               (x == N - 1 && y == 0) ||
               (x == 0 && y == M - 1);
    }

    static void paths(int x, int y, int N, int M, StringBuilder curr,
                      String[] maze, boolean[][] vis, List<String> validPaths) {
        if (checkDest(x, y, N, M)) {
            validPaths.add(curr.toString());
            return;
        }

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            char direction = dir[i];

            if (isValid(newX, newY, N, M, vis, maze)) {
                vis[newX][newY] = true;
                curr.append(direction);
                paths(newX, newY, N, M, curr, maze, vis, validPaths);
                curr.deleteCharAt(curr.length() - 1);
                vis[newX][newY] = false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        sc.nextLine();
        String[] maze = new String[N];
        for (int i = 0; i < N; i++) {
            maze[i] = sc.nextLine();
        }
        int X = sc.nextInt();
        int Y = sc.nextInt();

        boolean[][] vis = new boolean[N][M];
        List<String> validPaths = new ArrayList<>();
        vis[X][Y] = true;
        paths(X, Y, N, M, new StringBuilder(), maze, vis, validPaths);

        for (String path : validPaths) {
            System.out.println(path);
        }
        sc.close();
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dir = ['U', 'D', 'L', 'R']

def isValid(x, y, N, M, vis, maze):
    if x < 0 or y < 0 or x >= N or y >= M:
        return False
    if vis[x][y]:
        return False
    if maze[x][y] == '#':
        return False
    return True

def checkDest(x, y, N, M):
    return (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)

def paths(x, y, N, M, curr, maze, vis, validPaths):
    if checkDest(x, y, N, M):
        validPaths.append(curr)
        return
    for i in range(4):
        newX = x + dx[i]
        newY = y + dy[i]
        direction = dir[i]
        if isValid(newX, newY, N, M, vis, maze):
            vis[newX][newY] = True
            paths(newX, newY, N, M, curr + direction, maze, vis, validPaths)
            vis[newX][newY] = False

def main():
    N, M = map(int, input().split())
    maze = [input().strip() for _ in range(N)]
    X, Y = map(int, input().split())

    vis = [[False] * M for _ in range(N)]
    validPaths = []
    vis[X][Y] = True
    paths(X, Y, N, M, "", maze, vis, validPaths)

    for path in validPaths:
        print(path)

if __name__ == "__main__":
    main()

You can also try this code with Online Python Compiler

Run Code

Dry Run

Time Complexity

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

Space Complexity

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

Frequently Asked Questions

What is Backtracking?

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

What are the four corners of a matrix?

The four corners of a matrix are the cells located at:

Top-left: (0, 0)
Top-right: (0, n - 1)
Bottom-left: (m - 1, 0)
Bottom-right: (m - 1, n - 1)
Here, m is the number of rows and n is the number of columns. These corners are considered as destinations when finding paths from a given source point.

What techniques are used to find all paths in a matrix?

To find all paths from a source to the corners, we commonly use recursion and backtracking. These techniques allow us to explore every possible path while avoiding out-of-bound errors and revisiting the same cell in a single path. We can also use helper functions to track the current path and print it when a corner is reached.

Can we optimize the solution for larger matrices?

Yes. For larger matrices, recursive solutions can become slow due to repeated calculations. To optimize:

Use memoization to store intermediate results.
Apply pruning to avoid paths that are guaranteed not to reach a corner.
Consider using BFS or DFS with iterative stacks if recursion depth becomes a problem.

Conclusion

Finding all paths from a source point to the four corners of a matrix is a classic problem that helps strengthen your understanding of recursion, backtracking, and matrix traversal techniques. By exploring every possible route and carefully handling boundary and obstacle conditions, you can solve complex pathfinding challenges effectively. This problem not only improves your algorithmic thinking but also lays the foundation for tackling real-world scenarios involving grids and graphs.

8 Queens Problem Using Backtracking

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!