Print all paths from a source point to all the 4 corners of a Matrix - Coding

Given a 2D array arr[][] of size M*N containing 1s and 0s where 1 represents that the cell can be visited and 0s represent that the cell is blocked. There is a source point (x, y) and the task is to print all the paths from the given source to any of the four corners of the array (0, 0), (0, N – 1), (M – 1, 0) and (M – 1, N – 1).

Examples:

Input: arr[][] = {{1, 0, 0, 1, 0, 0, 1, 1}, {1, 1, 1, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 1, 0, 0, 1}, {0, 1, 1, 1, 1, 0, 0, 1}, {0, 1, 0, 0, 1, 1, 1, 1}, {1, 1, 0, 0, 0, 0, 0, 1} }. source = {4, 2}
Output : {“DRRUUURRUUR”, “DRRUUULLULLU”, “DRRDRRRD”, “DLDDL”}
Explanation : All the possible paths from the source to the 4 corners are

Input: arr[][] = {{0, 1, 0}, {0, 0, 0}, {0, 0, 0}}, source = {0, 1}
Output: No possible path

Approach: The idea is to use recursion and backtracking to find all possible paths by considering each possible path from a source to a destination and store it if it is a valid path. Follow the steps below to solve the problem:

Initialize a vector of strings ans[] to store the answer.
Recursively call the function to check in each of the 4 directions while pushing the current direction and making the cell visited.
If either the pointer crosses the boundary or the cell to visit is not a valid cell i.e, its value is 0 then return.
Otherwise, store the current cell and on reaching to any of the ends, then make it as one of the results.
After performing the above steps, print the array ans[].

Below is the implementation of the above approach.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
struct direction {
    int x, y;
    char c;
};
 
// Function to check if we reached on
// of the entry/exit (corner) point.
bool isCorner(int i, int j, int M, int N)
{
    if ((i == 0 && j == 0)
        || (i == 0 && j == N - 1)
        || (i == M - 1 && j == N - 1)
        || (i == M - 1 && j == 0))
        return true;
 
    return false;
}
 
// Function to check if the index is
// within the matrix boundary.
bool isValid(int i, int j, int M, int N)
{
    if (i < 0 || i >= M || j < 0 || j >= N)
        return false;
    return true;
}
 
// Recursive helper function
void solve(int i, int j, int M, int N,
           direction dir[],
           vector<vector<int> >& maze,
           string& t, vector<string>& ans)
{
 
    // If any corner is reached push the
    // string t into ans and return
    if (isCorner(i, j, M, N)) {
        ans.push_back(t);
        return;
    }
 
    // For all the four directions
    for (int k = 0; k < 4; k++) {
 
        // The new ith index
        int x = i + dir[k].x;
 
        // The new jth index
        int y = j + dir[k].y;
 
        // The direction R/L/U/D
        char c = dir[k].c;
 
        // If the new cell is within the
        // matrix boundary and it is not
        // previously visited in same path
        if (isValid(x, y, M, N)
            && maze[x][y] == 1) {
 
            // Mark the new cell as visited
            maze[x][y] = 0;
 
            // Store the direction
            t.push_back(c);
 
            // Recur
            solve(x, y, M, N, dir,
                  maze, t, ans);
 
            // Backtrack to explore
            // other paths
            t.pop_back();
            maze[x][y] = 1;
        }
    }
    return;
}
 
// Function to find all possible paths
vector<string> possiblePaths(
    vector<int> src, vector<vector<int> >& maze)
{
    // Create a direction  array for all
    // the four directions
    direction dir[4] = { { -1, 0, 'U' },
                         { 0, 1, 'R' },
                         { 1, 0, 'D' },
                         { 0, -1, 'L' } };
 
    // Stores the result
    string temp;
    vector<string> ans;
 
    solve(src[0], src[1], maze.size(),
          maze[0].size(), dir,
          maze, temp, ans);
 
    return ans;
}
 
// Driver Code
int main()
{
 
    // Initializing the variables
    vector<vector<int> > maze = {
        { 1, 0, 0, 1, 0, 0, 1, 1 },
        { 1, 1, 1, 0, 0, 0, 1, 0 },
        { 1, 0, 1, 1, 1, 1, 1, 0 },
        { 0, 0, 0, 0, 1, 0, 0, 0 },
        { 1, 0, 1, 0, 1, 0, 0, 1 },
        { 0, 1, 1, 1, 1, 0, 0, 1 },
        { 0, 1, 0, 0, 1, 1, 1, 1 },
        { 1, 1, 0, 0, 0, 0, 0, 1 },
    };
    vector<int> src = { 4, 2 };
 
    // Function Call
    vector<string> paths
        = possiblePaths(src, maze);
 
    // Print the result
    if (paths.size() == 0) {
        cout << "No Possible Paths";
        return 0;
    }
 
    for (int i = 0; i < paths.size(); i++)
        cout << paths[i] << endl;
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
public class GFG {
 
  static class direction {
    int x, y;
    char c;
    direction(int x, int y, char c)
    {
      this.c = c;
      this.x = x;
      this.y = y;
    }
  };
 
  // Function to check if we reached on
  // of the entry/exit (corner) point.
  static boolean isCorner(int i, int j, int M, int N)
  {
    if ((i == 0 && j == 0) || (i == 0 && j == N - 1)
        || (i == M - 1 && j == N - 1)
        || (i == M - 1 && j == 0))
      return true;
 
    return false;
  }
 
  // Function to check if the index is
  // within the matrix boundary.
  static boolean isValid(int i, int j, int M, int N)
  {
    if (i < 0 || i >= M || j < 0 || j >= N)
      return false;
    return true;
  }
 
  // Recursive helper function
  static void solve(int i, int j, int M, int N,
                    direction dir[], int[][] maze,
                    String t, ArrayList<String> ans)
  {
 
    // If any corner is reached push the
    // string t into ans and return
    if (isCorner(i, j, M, N)) {
      ans.add(t);
      return;
    }
 
    // For all the four directions
    for (int k = 0; k < 4; k++) {
 
      // The new ith index
      int x = i + dir[k].x;
 
      // The new jth index
      int y = j + dir[k].y;
 
      // The direction R/L/U/D
      char c = dir[k].c;
 
      // If the new cell is within the
      // matrix boundary and it is not
      // previously visited in same path
      if (isValid(x, y, M, N) && maze[x][y] == 1) {
 
        // Mark the new cell as visited
        maze[x][y] = 0;
 
        // Store the direction
        t += c;
 
        // Recur
        solve(x, y, M, N, dir, maze, t, ans);
 
        // Backtrack to explore
        // other paths
        t = t.substring(0, t.length() - 1);
        maze[x][y] = 1;
      }
    }
    return;
  }
 
  // Function to find all possible paths
  static ArrayList<String> possiblePaths(int[] src,
                                         int[][] maze)
  {
    // Create a direction array for all
    // the four directions
    direction[] dir = { new direction(-1, 0, 'U'),
                       new direction(0, 1, 'R'),
                       new direction(1, 0, 'D'),
                       new direction(0, -1, 'L') };
 
    // Stores the result
    String temp = "";
    ArrayList<String> ans = new ArrayList<>();
 
    solve(src[0], src[1], maze.length, maze[0].length,
          dir, maze, temp, ans);
 
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Initializing the variables
    int[][] maze = {
      { 1, 0, 0, 1, 0, 0, 1, 1 },
      { 1, 1, 1, 0, 0, 0, 1, 0 },
      { 1, 0, 1, 1, 1, 1, 1, 0 },
      { 0, 0, 0, 0, 1, 0, 0, 0 },
      { 1, 0, 1, 0, 1, 0, 0, 1 },
      { 0, 1, 1, 1, 1, 0, 0, 1 },
      { 0, 1, 0, 0, 1, 1, 1, 1 },
      { 1, 1, 0, 0, 0, 0, 0, 1 },
    };
    int[] src = { 4, 2 };
 
    // Function Call
    ArrayList<String> paths = possiblePaths(src, maze);
 
    // Print the result
    if (paths.size() == 0) {
      System.out.println("No Possible Paths");
      return;
    }
 
    for (int i = 0; i < paths.size(); i++) {
      System.out.println(paths.get(i));
    }
  }
}
// This code is contributed by Karandeep1234

Python3

# Python program for the above approach
 
# Function to check if we reached on
# of the entry/exit (corner) point.
def isCorner(i, j, M, N):
    if((i == 0 and j == 0) or (i == 0 and j == N-1) or (i == M-1 and j == N-1) or (i == M-1 and j == 0)):
        return True
    return False
 
# Function to check if the index is
# within the matrix boundary.
def isValid(i, j, M, N):
    if(i < 0 or i >= M or j < 0 or j >= N):
        return False
    return True
 
# Recursive helper function
def solve(i, j, M, N, Dir, maze, t, ans):
   
    # If any corner is reached push the
    # string t into ans and return
    if(isCorner(i, j, M, N)):
        ans.append(t)
        return
       
    # For all the four directions
    for k in range(4):
       
      # The new ith index
        x = i + Dir[k][0]
         
        # The new jth index
        y = j + Dir[k][1]
         
        # The direction R/L/U/D
        c = Dir[k][2]
         
         # If the new cell is within the
        # matrix boundary and it is not
        # previously visited in same path
        if(isValid(x, y, M, N) and maze[x][y] == 1):
           
          # mark the new cell visited
            maze[x][y] = 0
             
            # Store the direction
            t += c
            solve(x, y, M, N, Dir, maze, t, ans)
             
             # Backtrack to explore
            # other paths
            t = t[: len(t)-1]
            maze[x][y] = 1
    return
 
# Function to find all possible paths
def possiblePaths(src, maze):
   
     # Create a direction  array for all
    # the four directions
    Dir = [[-1, 0, 'U'], [0, 1, 'R'], [1, 0, 'D'], [0, -1, 'L']]
     
    # stores the result  
    temp = ""
    ans = []
    solve(src[0], src[1], len(maze), len(maze[0]), Dir, maze, temp, ans)
    return ans
 
# Driver code
 
# Initialise variable
maze = [[1, 0, 0, 1, 0, 0, 1, 1],
        [1, 1, 1, 0, 0, 0, 1, 0],
        [1, 0, 1, 1, 1, 1, 1, 0],
        [0, 0, 0, 0, 1, 0, 0, 0],
        [1, 0, 1, 0, 1, 0, 0, 1],
        [0, 1, 1, 1, 1, 0, 0, 1],
        [0, 1, 0, 0, 1, 1, 1, 1],
        [1, 1, 0, 0, 0, 0, 0, 1]]
src = [4, 2]
 
# function call
paths = possiblePaths(src, maze)
 
# Print the result
if(len(paths) == 0):
    print("No Possible Paths")
else:
    for i in paths:
        print(i)
 
# This code is contributed by parthmanchanda81

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class Direction
{
  public int x, y;
  public char c;
};
 
public class Program
{
 
  // Function to check if we reached on
  // of the entry/exit (corner) point.
  public static bool IsCorner(int i, int j, int M, int N)
  {
    if ((i == 0 && j == 0)
        || (i == 0 && j == N - 1)
        || (i == M - 1 && j == N - 1)
        || (i == M - 1 && j == 0))
      return true;
 
    return false;
  }
  // Function to check if the index is
  // within the matrix boundary.
  public static bool IsValid(int i, int j, int M, int N)
  {
    if (i < 0 || i >= M || j < 0 || j >= N)
      return false;
    return true;
  }
  // Recursive function for helper
  public static void Solve(int i, int j, int M, int N,
                           Direction[] dir,
                           List<List<int>> maze,
                           ref string t, List<string> ans)
  {
    // If any corner is reached push the
    // string t into ans and return
    if (IsCorner(i, j, M, N))
    {
      ans.Add(t);
      return;
    }
    // For all the four directions
    for (int k = 0; k < 4; k++)
    {
 
      // The new ith index
      int x = i + dir[k].x;
 
 
      // The new jth index
      int y = j + dir[k].y;
 
      // The direction R/L/U/D
      char c = dir[k].c;
 
      // If the new cell is within the
      // matrix boundary and it is not
      // previously visited in same path
      if (IsValid(x, y, M, N)
          && maze[x][y] == 1)
      {  
        // Mark the new cell as visited
        maze[x][y] = 0;
        t += c;    // Store the direction
        // call recursion
        Solve(x, y, M, N, dir,
              maze, ref t, ans);
 
        // Backtrack to explore
        // other paths
        t = t.Remove(t.Length - 1);
        maze[x][y] = 1;
      }
    }
    return;
  }
 
  // Function to find all possible paths
  public static List<string> PossiblePaths(List<int> src, List<List<int>> maze)
  {
    // Create a direction  array for all
    // the four directions
    Direction[] dir = {
      new Direction { x = -1, y = 0, c = 'U' },
      new Direction { x = 0, y = 1, c = 'R' },
      new Direction { x = 1, y = 0, c = 'D' },
      new Direction { x = 0, y = -1, c = 'L' }
    };
 
    // Stores the result
    string temp = "";
    List<string> ans = new List<string>();
 
    Solve(src[0], src[1], maze.Count,
          maze[0].Count, dir,
          maze, ref temp, ans);
 
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
     
    // Initializing the variables
    List<List<int>> maze = new List<List<int>> {
      new List<int>() { 1, 0, 0, 1, 0, 0, 1, 1 },
      new List<int>() { 1, 1, 1, 0, 0, 0, 1, 0 },
      new List<int>() { 1, 0, 1, 1, 1, 1, 1, 0 },
      new List<int>() { 0, 0, 0, 0, 1, 0, 0, 0 },
      new List<int>() { 1, 0, 1, 0, 1, 0, 0, 1 },
      new List<int>() { 0, 1, 1, 1, 1, 0, 0, 1 },
      new List<int>() { 0, 1, 0, 0, 1, 1, 1, 1 },
      new List<int>() { 1, 1, 0, 0, 0, 0, 0, 1 },
    };
    List<int> src = new List<int>() { 4, 2 };
 
    List<string> paths = PossiblePaths(src, maze);
 
    // Print the result
    if (paths.Capacity == 0) {
      Console.WriteLine("No Possible Paths");
      return;
    }
    for (int i = 0; i < paths.Capacity; i++)
      Console.WriteLine(paths[i]);
    return;
  }}

Javascript

<script>
// Javascript program for the above approach
 
// Function to check if we reached on
// of the entry/exit (corner) point.
function isCorner(i, j, M, N) {
  if (
    (i == 0 && j == 0) ||
    (i == 0 && j == N - 1) ||
    (i == M - 1 && j == N - 1) ||
    (i == M - 1 && j == 0)
  )
    return true;
  return false;
}
 
// Function to check if the index is
// within the matrix boundary.
function isValid(i, j, M, N) {
  if (i < 0 || i >= M || j < 0 || j >= N) return false;
  return true;
}
 
// Recursive helper function
function solve(i, j, M, N, Dir, maze, t, ans) {
  // If any corner is reached push the
  // string t into ans and return
  if (isCorner(i, j, M, N)) {
    ans.push(t);
    return;
  }
 
  // For all the four directions
  for (let k = 0; k < 4; k++) {
    // The new ith index
    let x = i + Dir[k][0];
 
    // The new jth index
    let y = j + Dir[k][1];
 
    // The direction R/L/U/D
    let c = Dir[k][2];
 
    // If the new cell is within the
    // matrix boundary and it is not
    // previously visited in same path
    if (isValid(x, y, M, N) && maze[x][y] == 1) {
      // mark the new cell visited
      maze[x][y] = 0;
 
      // Store the direction
      t += c;
      solve(x, y, M, N, Dir, maze, t, ans);
 
      // Backtrack to explore
      // other paths
 
      t = t.substr(0, t.length - 1);
      maze[x][y] = 1;
    }
  }
  return;
}
 
// Function to find all possible paths
function possiblePaths(src, maze) {
  // Create a direction  array for all
  // the four directions
  let Dir = [
    [-1, 0, "U"],
    [0, 1, "R"],
    [1, 0, "D"],
    [0, -1, "L"],
  ];
 
  // stores the result
  let temp = "";
  let ans = [];
  solve(src[0], src[1], maze.length, maze[0].length, Dir, maze, temp, ans);
  return ans;
}
 
// Driver code
 
// Initialise variable
let maze = [
  [1, 0, 0, 1, 0, 0, 1, 1],
  [1, 1, 1, 0, 0, 0, 1, 0],
  [1, 0, 1, 1, 1, 1, 1, 0],
  [0, 0, 0, 0, 1, 0, 0, 0],
  [1, 0, 1, 0, 1, 0, 0, 1],
  [0, 1, 1, 1, 1, 0, 0, 1],
  [0, 1, 0, 0, 1, 1, 1, 1],
  [1, 1, 0, 0, 0, 0, 0, 1],
];
let src = [4, 2];
 
// function call
let paths = possiblePaths(src, maze);
 
// Print the result
if (paths.length == 0) {
  document.write("No Possible Paths");
} else {
  for (let i = 0; i < paths.length; i++) {
    if (paths[i]) document.write(paths[i] + "<Br>");
  }
}
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Output:

DRRUUURRUUR
DRRUUULLULLU
DRRDRRRD
DLDDL

Time Complexity: O(3^(M*N))
Auxiliary Space: O(3^(M*N))

Reffered: https://www.geeksforgeeks.org

Matrix

Related
Form a Rectangle from boundary elements of Matrix using Linked List
Maximize matrix sum by flipping the sign of any adjacent pairs
Rabbit House \| Google Kickstart 2021 Round A
Maximum points by traversing from top left of Matrix to bottom right by two persons
Print all possible paths to escape out of a matrix from a given position using at most K moves

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11