Print all unique paths from given source to destination in a Matrix moving only down or right
Given a 2-D array mat[][], a source βsβ and a destination βdβ, print all unique paths from given βsβ to βdβ. From each cell, you can either move only to the right or down.
Examples:
Input: mat[][] = {{1, 2, 3}, {4, 5, 6}}, s[] = {0, 0}, d[]={1, 2}
Output:
1 4 5 6
1 2 5 6
1 2 3 6Input: mat[][] = {{1, 2}, {3, 4}}, s[] = {0, 1}, d[] = {1, 1}
Output: 2 4
Approach: Use recursion to move first right then down from each cell in the path of the matrix mat[][], starting from source, and store each value in a vector. If the destination is reached, print the vector as one of the possible paths. Follow the steps below to solve the problem:
- If the current cell is out of the boundary, then return.
- Push the current cellβs value into the vector path[].
- If the current cell is the destination, then print the current path.
- Call the same function for the values {i+1, j} and {i, j+1}.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; vector<vector< int > > mat; vector< int > s; vector< int > d; int m = 2, n = 3; // Function to print all the paths void printVector(vector< int > path) { int cnt = path.size(); for ( int i = 0; i < cnt; i += 2) cout << mat[path[i]][path[i + 1]] << " " ; cout << endl; } // Function to find all the paths recursively void countPaths( int i, int j, vector< int > path) { // Base Case if (i > d[0] || j > d[1]) return ; path.push_back(i); path.push_back(j); // Destination is reached if (i == d[0] && j == d[1]) { printVector(path); return ; } // Calling the function countPaths(i, j + 1, path); countPaths(i + 1, j, path); } // DriverCode int main() { mat = { { 1, 2, 3 }, { 4, 5, 6 } }; s = { 0, 0 }; d = { 1, 2 }; vector< int > path; countPaths(s[0], s[1], path); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { static Vector<Integer> s = new Vector<>(); static Vector<Integer> d = new Vector<>(); static int m = 2 , n = 3 ; // Function to print all the paths static void printVector(Vector<Integer> path, int [][] mat) { int cnt = path.size(); for ( int i = 0 ; i < cnt; i += 2 ) System.out.print(mat[path.get(i)][path.get(i + 1 )]+ " " ); System.out.println(); } // Function to find all the paths recursively static void countPaths( int i, int j, Vector<Integer> path, int [][]mat) { // Base Case if (i > d.get( 0 ) || j > d.get( 1 )) return ; path.add(i); path.add(j); // Destination is reached if (i == d.get( 0 ) && j == d.get( 1 )) { printVector(path,mat); path.remove(path.size()- 1 ); path.remove(path.size()- 1 ); return ; } // Calling the function countPaths(i, j + 1 , path,mat); countPaths(i + 1 , j, path,mat); path.remove(path.size()- 1 ); path.remove(path.size()- 1 ); } // DriverCode public static void main(String[] args) { int [][] mat = {{ 1 , 2 , 3 }, { 4 , 5 , 6 } }; s.add( 0 ); s.add( 0 ); d.add( 1 ); d.add( 2 ); Vector<Integer> path = new Vector<>(); countPaths(s.get( 0 ), s.get( 1 ), path, mat); } } // This code is contributed by Rajput-Ji. |
Python3
# Python code for the above approach mat = None s = None d = None m = 2 n = 3 # Function to print all the paths def printVector(path): cnt = len (path) for i in range ( 0 , cnt, 2 ): print (mat[path[i]][path[i + 1 ]], end = " " ) print ("") # Function to find all the paths recursively def countPaths(i, j, path): # Base Case if (i > d[ 0 ] or j > d[ 1 ]): return path.append(i) path.append(j) # Destination is reached if (i = = d[ 0 ] and j = = d[ 1 ]): printVector(path) path.pop() path.pop() return # Calling the function countPaths(i, j + 1 , path) countPaths(i + 1 , j, path) path.pop() path.pop() # DriverCode mat = [[ 1 , 2 , 3 ], [ 4 , 5 , 6 ]] s = [ 0 , 0 ] d = [ 1 , 2 ] path = [] countPaths(s[ 0 ], s[ 1 ], path) # This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { static List< int > s = new List< int >(); static List< int > d = new List< int >(); static int m = 2, n = 3; // Function to print all the paths static void printList(List< int > path, int [,] mat) { int cnt = path.Count; for ( int i = 0; i < cnt; i += 2) Console.Write(mat[path[i],path[i + 1]] + " " ); Console.WriteLine(); } // Function to find all the paths recursively static void countPaths( int i, int j, List< int > path, int [,] mat) { // Base Case if (i > d[0] || j > d[1]) return ; path.Add(i); path.Add(j); // Destination is reached if (i == d[0] && j == d[1]) { printList(path, mat); path.RemoveAt(path.Count - 1); path.RemoveAt(path.Count - 1); return ; } // Calling the function countPaths(i, j + 1, path, mat); countPaths(i + 1, j, path, mat); path.RemoveAt(path.Count - 1); path.RemoveAt(path.Count - 1); } // DriverCode public static void Main(String[] args) { int [,] mat = { { 1, 2, 3 }, { 4, 5, 6 } }; s.Add(0); s.Add(0); d.Add(1); d.Add(2); List< int > path = new List< int >(); countPaths(s[0], s[1], path, mat); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript code for the above approach let mat; let s; let d; let m = 2, n = 3; // Function to print all the paths function printVector(path) { let cnt = path.length; for (let i = 0; i < cnt; i += 2) document.write(mat[path[i]][path[i + 1]] + " " ) document.write( "<br>" ) } // Function to find all the paths recursively function countPaths(i, j, path) { // Base Case if (i > d[0] || j > d[1]) return ; path.push(i); path.push(j); // Destination is reached if (i == d[0] && j == d[1]) { printVector(path); path.pop(); path.pop(); return ; } // Calling the function countPaths(i, j + 1, path); countPaths(i + 1, j, path); path.pop(); path.pop(); } // DriverCode mat = [[1, 2, 3], [4, 5, 6]]; s = [0, 0]; d = [1, 2]; let path = []; countPaths(s[0], s[1], path); // This code is contributed by Potta Lokesh </script> |
Output:
1 2 3 6 1 2 5 6 1 4 5 6
Time Complexity: O(2n+m)
Auxiliary Space: O(1)