Posted on by Kalkicode
Code Matrix

Print all possible paths from top left to bottom right of matrix

The problem entails generating and printing all possible paths from the top-left corner to the bottom-right corner of a matrix. These paths can only move downwards or to the right. The task is to display all such paths in the given matrix.

Print all possible paths in given position

Problem Statement

Given a matrix of characters, we need to find and print all possible paths from the top-left corner to the bottom-right corner of the matrix. The paths can only move in the downward and rightward directions.

Example

Consider the following matrix:

A B C D
E F G H
I J K L
M N O P
Q R S T

The possible paths from the top-left corner (A) to the bottom-right corner (T) are as follows:

  1. A E I M Q R S T
  2. A E I M N R S T
  3. A E I M N O S T
  4. A E I M N O P T
  5. A E I J N R S T
  6. A E I J N O S T
  7. A E I J N O P T
  8. A E I J K O S T
  9. A E I J K O P T
  10. A E I J K L P T
  11. A E F J N R S T
  12. A E F J N O S T
  13. A E F J N O P T
  14. A E F J K O S T
  15. A E F J K O P T
  16. A E F J K L P T
  17. A E F G K O S T
  18. A E F G K O P T
  19. A E F G K L P T
  20. A E F G H L P T
  21. A B F J N R S T
  22. A B F J N O S T
  23. A B F J N O P T
  24. A B F J K O S T
  25. A B F J K O P T
  26. A B F J K L P T
  27. A B F G K O S T
  28. A B F G K O P T
  29. A B F G K L P T
  30. A B F G H L P T
  31. A B C G K O S T
  32. A B C G K O P T
  33. A B C G K L P T
  34. A B C D H L P T

Idea to Solve

To solve this problem, we can use a recursive approach. At each step, we have two options: move downward or move to the right. We recursively explore both options while keeping track of the path we have taken so far.

Pseudocode

Here's the pseudocode to solve the problem:

function showPaths(matrix, result, row, col, count, k):
    if row >= R or col >= C:
        return

    result[count] = matrix[row][col]

    showPaths(matrix, result, row+1, col, count+1, k)
    showPaths(matrix, result, row, col+1, count+1, k)

    if count + 1 == k:
        print result

function main():
    define matrix
    define result array
    showPaths(matrix, result, 0, 0, 0, R+C-1)

main()

Algorithm Explanation

  1. At each step, place the character at the current cell into the result array.
  2. Recursively explore the downward and rightward paths from the current cell, increasing the count by 1.
  3. If the count becomes equal to the total length of the path (sum of rows and columns - 1), print the result array.
  4. The recursion continues until either the row index or the column index goes beyond the matrix boundaries.

Code Solution

//C Program
//Print all possible paths from top left to bottom right of matrix
#include<stdio.h>


#define R 5 
#define C 4 
//Display of all path of top to bottom and left to right
void show_path(char mat[R][C],char result[],int row ,int col,int count,int k)
{

  if(row >= R || col >= C)
  {
    return;
  }

  result[count]=mat[row][col];
  //recursive execute method with new parameters
  show_path(mat,result,row+1,col,count+1,k);
  show_path(mat,result,row,col+1,count+1,k);
  
  if(count+1==k)
  {
    //Display the result value
    for (int i = 0; i <k; ++i)
    { 
      printf("%3c",result[i]);
    }
    printf("\n");
  }
}


int main()
{
  char mat[R][C] = { 
    {'A', 'B', 'C', 'D'}, 
    {'E', 'F', 'G', 'H'}, 
    {'I', 'J', 'K', 'L'},
    {'M', 'N', 'O', 'P'},
    {'Q', 'R', 'S', 'T'},
  };
  //Auxiliary memory which are storing path result
  char result[R+C-1];
  show_path(mat,result,0,0,0,R+C-1);

  return 0;
}

Output

  A  E  I  M  Q  R  S  T
  A  E  I  M  N  R  S  T
  A  E  I  M  N  O  S  T
  A  E  I  M  N  O  P  T
  A  E  I  J  N  R  S  T
  A  E  I  J  N  O  S  T
  A  E  I  J  N  O  P  T
  A  E  I  J  K  O  S  T
  A  E  I  J  K  O  P  T
  A  E  I  J  K  L  P  T
  A  E  F  J  N  R  S  T
  A  E  F  J  N  O  S  T
  A  E  F  J  N  O  P  T
  A  E  F  J  K  O  S  T
  A  E  F  J  K  O  P  T
  A  E  F  J  K  L  P  T
  A  E  F  G  K  O  S  T
  A  E  F  G  K  O  P  T
  A  E  F  G  K  L  P  T
  A  E  F  G  H  L  P  T
  A  B  F  J  N  R  S  T
  A  B  F  J  N  O  S  T
  A  B  F  J  N  O  P  T
  A  B  F  J  K  O  S  T
  A  B  F  J  K  O  P  T
  A  B  F  J  K  L  P  T
  A  B  F  G  K  O  S  T
  A  B  F  G  K  O  P  T
  A  B  F  G  K  L  P  T
  A  B  F  G  H  L  P  T
  A  B  C  G  K  O  S  T
  A  B  C  G  K  O  P  T
  A  B  C  G  K  L  P  T
  A  B  C  G  H  L  P  T
  A  B  C  D  H  L  P  T
/*
  C++ Program
  Print all possible paths from top left to bottom right of matrix
*/
#include<iostream>
#define R 5 
#define C 4 
using namespace std;


class MyMatrix {
	public:
	int rows;
	int cols;

	//Display of all path of top to bottom and left to right
	void show_path(char matrix[][C], char result[], int row, int col, int count, int k) {
		if (row >= R || col >= C) {
			return;
		}
		result[count] = matrix[row][col];
		//recursive execute method with new parameters
		this->show_path(matrix, result, row + 1, col, count + 1, k);
		this->show_path(matrix, result, row, col + 1, count + 1, k);
		if (count + 1 == k) {
			//Display the result value

			for (int i = 0; i < k; ++i) {
				cout << "  " << result[i];
			}
			cout << "\n";
		}
	}
};
int main() {
	char matrix[][C] = {
		{
			'A',
			'B',
			'C',
			'D'
		},
		{
			'E',
			'F',
			'G',
			'H'
		},
		{
			'I',
			'J',
			'K',
			'L'
		},
		{
			'M',
			'N',
			'O',
			'P'
		},
		{
			'Q',
			'R',
			'S',
			'T'
		},
		
	};
	MyMatrix obj = MyMatrix();
	char result[R + C - 1];
	obj.show_path(matrix, result, 0, 0, 0, R + C - 1);
	return 0;
}

Output

  A  E  I  M  Q  R  S  T
  A  E  I  M  N  R  S  T
  A  E  I  M  N  O  S  T
  A  E  I  M  N  O  P  T
  A  E  I  J  N  R  S  T
  A  E  I  J  N  O  S  T
  A  E  I  J  N  O  P  T
  A  E  I  J  K  O  S  T
  A  E  I  J  K  O  P  T
  A  E  I  J  K  L  P  T
  A  E  F  J  N  R  S  T
  A  E  F  J  N  O  S  T
  A  E  F  J  N  O  P  T
  A  E  F  J  K  O  S  T
  A  E  F  J  K  O  P  T
  A  E  F  J  K  L  P  T
  A  E  F  G  K  O  S  T
  A  E  F  G  K  O  P  T
  A  E  F  G  K  L  P  T
  A  E  F  G  H  L  P  T
  A  B  F  J  N  R  S  T
  A  B  F  J  N  O  S  T
  A  B  F  J  N  O  P  T
  A  B  F  J  K  O  S  T
  A  B  F  J  K  O  P  T
  A  B  F  J  K  L  P  T
  A  B  F  G  K  O  S  T
  A  B  F  G  K  O  P  T
  A  B  F  G  K  L  P  T
  A  B  F  G  H  L  P  T
  A  B  C  G  K  O  S  T
  A  B  C  G  K  O  P  T
  A  B  C  G  K  L  P  T
  A  B  C  G  H  L  P  T
  A  B  C  D  H  L  P  T
/*
  Java Program
  Print all possible paths from top left to bottom right of matrix
*/

public class MyMatrix {
  public int rows;
  public int cols;
  public MyMatrix(char [][]matrix)
  {
    //Get the size of matrix
    rows = matrix.length;
    cols = matrix[0].length;
  }

  //Display of all path of top to bottom and left to right
  void show_path(char [][]matrix,char []result,int row ,int col,int count,int k)
  {

    if(row >= this.rows || col >= this.cols)
    {
      return;
    }

    result[count]=matrix[row][col];
    //recursive execute method with new parameters
    show_path(matrix,result,row+1,col,count+1,k);
    show_path(matrix,result,row,col+1,count+1,k);
    
    if(count+1==k)
    {
      //Display the result value
      for (int i = 0; i <k; ++i)
      { 
        System.out.print("  "+result[i]);
      }
      System.out.print("\n");
    }
  }

 
  public static void main(String[] args) {

    
    char [][]matrix = { 
      {'A', 'B', 'C', 'D'}, 
      {'E', 'F', 'G', 'H'}, 
      {'I', 'J', 'K', 'L'},
      {'M', 'N', 'O', 'P'},
      {'Q', 'R', 'S', 'T'},
    };
    MyMatrix obj = new MyMatrix(matrix);

    //Auxiliary memory which are storing path result
    char []result= new char[obj.rows+obj.cols-1];

    obj.show_path(matrix,result,0,0,0,obj.rows+obj.cols-1);
  }
}

Output

  A  E  I  M  Q  R  S  T
  A  E  I  M  N  R  S  T
  A  E  I  M  N  O  S  T
  A  E  I  M  N  O  P  T
  A  E  I  J  N  R  S  T
  A  E  I  J  N  O  S  T
  A  E  I  J  N  O  P  T
  A  E  I  J  K  O  S  T
  A  E  I  J  K  O  P  T
  A  E  I  J  K  L  P  T
  A  E  F  J  N  R  S  T
  A  E  F  J  N  O  S  T
  A  E  F  J  N  O  P  T
  A  E  F  J  K  O  S  T
  A  E  F  J  K  O  P  T
  A  E  F  J  K  L  P  T
  A  E  F  G  K  O  S  T
  A  E  F  G  K  O  P  T
  A  E  F  G  K  L  P  T
  A  E  F  G  H  L  P  T
  A  B  F  J  N  R  S  T
  A  B  F  J  N  O  S  T
  A  B  F  J  N  O  P  T
  A  B  F  J  K  O  S  T
  A  B  F  J  K  O  P  T
  A  B  F  J  K  L  P  T
  A  B  F  G  K  O  S  T
  A  B  F  G  K  O  P  T
  A  B  F  G  K  L  P  T
  A  B  F  G  H  L  P  T
  A  B  C  G  K  O  S  T
  A  B  C  G  K  O  P  T
  A  B  C  G  K  L  P  T
  A  B  C  G  H  L  P  T
  A  B  C  D  H  L  P  T
/*
  C# Program
  Print all possible paths from top left to bottom right of matrix
*/
using System;

public class MyMatrix {
	public int rows;
	public int cols;
	public MyMatrix(char[,] matrix) {
		//Get the size of matrix
		rows = matrix.GetLength(0);
		cols = matrix.GetLength(1);
	}
	//Display of all path of top to bottom and left to right
	void show_path(char[,] matrix, char[] result, int row, int col, int count, int k) {
		if (row >= this.rows || col >= this.cols) {
			return;
		}
		result[count] = matrix[row,col];
		show_path(matrix, result, row + 1, col, count + 1, k);
		show_path(matrix, result, row, col + 1, count + 1, k);
		if (count + 1 == k) {
			//Display the result value

			for (int i = 0; i < k; ++i) {
				Console.Write("  " + result[i]);
			}
			Console.Write("\n");
		}
	}
	public static void Main(String[] args) {
		char[,] matrix = {
			{
				'A',
				'B',
				'C',
				'D'
			},
			{
				'E',
				'F',
				'G',
				'H'
			},
			{
				'I',
				'J',
				'K',
				'L'
			},
			{
				'M',
				'N',
				'O',
				'P'
			},
			{
				'Q',
				'R',
				'S',
				'T'
			},
		};
		MyMatrix obj = new MyMatrix(matrix);
		char[]
		//Auxiliary memory which are storing path result
		result = new char[obj.rows + obj.cols - 1];
		obj.show_path(matrix, result, 0, 0, 0, obj.rows + obj.cols - 1);
	}
}

Output

  A  E  I  M  Q  R  S  T
  A  E  I  M  N  R  S  T
  A  E  I  M  N  O  S  T
  A  E  I  M  N  O  P  T
  A  E  I  J  N  R  S  T
  A  E  I  J  N  O  S  T
  A  E  I  J  N  O  P  T
  A  E  I  J  K  O  S  T
  A  E  I  J  K  O  P  T
  A  E  I  J  K  L  P  T
  A  E  F  J  N  R  S  T
  A  E  F  J  N  O  S  T
  A  E  F  J  N  O  P  T
  A  E  F  J  K  O  S  T
  A  E  F  J  K  O  P  T
  A  E  F  J  K  L  P  T
  A  E  F  G  K  O  S  T
  A  E  F  G  K  O  P  T
  A  E  F  G  K  L  P  T
  A  E  F  G  H  L  P  T
  A  B  F  J  N  R  S  T
  A  B  F  J  N  O  S  T
  A  B  F  J  N  O  P  T
  A  B  F  J  K  O  S  T
  A  B  F  J  K  O  P  T
  A  B  F  J  K  L  P  T
  A  B  F  G  K  O  S  T
  A  B  F  G  K  O  P  T
  A  B  F  G  K  L  P  T
  A  B  F  G  H  L  P  T
  A  B  C  G  K  O  S  T
  A  B  C  G  K  O  P  T
  A  B  C  G  K  L  P  T
  A  B  C  G  H  L  P  T
  A  B  C  D  H  L  P  T
# Python 3 Program
# Print all possible paths from top left to bottom right of matrix
class MyMatrix :
	
	def __init__(self, matrix) :
		 # Get the size of matrix
		self.rows = len(matrix)
		self.cols = len(matrix[0])
	
	 # Display of all path of top to bottom and left to right
	def show_path(self, matrix, result, row, col, count, k) :
		if (row >= self.rows or col >= self.cols) :
			return
		
		result[count] = matrix[row][col]
		 # recursive execute method with new parameters
		self.show_path(matrix, result, row + 1, col, count + 1, k)
		self.show_path(matrix, result, row, col + 1, count + 1, k)
		if (count + 1 == k) :
			i = 0
			# Display the result value
			while (i < k) :
				print(" ", result[i], end = "")
				i += 1
			
			print("\n", end = "")
		
	

def main() :
	matrix = [
		['A', 'B', 'C', 'D'],
		['E', 'F', 'G', 'H'],
		['I', 'J', 'K', 'L'],
		['M', 'N', 'O', 'P'],
		['Q', 'R', 'S', 'T']
	]
	obj = MyMatrix(matrix)
	 # Auxiliary memory which are storing path result
	result = [' '] * (obj.rows + obj.cols - 1)
	obj.show_path(matrix, result, 0, 0, 0, obj.rows + obj.cols - 1)


if __name__ == "__main__":
	main()

Output

  A  E  I  M  Q  R  S  T
  A  E  I  M  N  R  S  T
  A  E  I  M  N  O  S  T
  A  E  I  M  N  O  P  T
  A  E  I  J  N  R  S  T
  A  E  I  J  N  O  S  T
  A  E  I  J  N  O  P  T
  A  E  I  J  K  O  S  T
  A  E  I  J  K  O  P  T
  A  E  I  J  K  L  P  T
  A  E  F  J  N  R  S  T
  A  E  F  J  N  O  S  T
  A  E  F  J  N  O  P  T
  A  E  F  J  K  O  S  T
  A  E  F  J  K  O  P  T
  A  E  F  J  K  L  P  T
  A  E  F  G  K  O  S  T
  A  E  F  G  K  O  P  T
  A  E  F  G  K  L  P  T
  A  E  F  G  H  L  P  T
  A  B  F  J  N  R  S  T
  A  B  F  J  N  O  S  T
  A  B  F  J  N  O  P  T
  A  B  F  J  K  O  S  T
  A  B  F  J  K  O  P  T
  A  B  F  J  K  L  P  T
  A  B  F  G  K  O  S  T
  A  B  F  G  K  O  P  T
  A  B  F  G  K  L  P  T
  A  B  F  G  H  L  P  T
  A  B  C  G  K  O  S  T
  A  B  C  G  K  O  P  T
  A  B  C  G  K  L  P  T
  A  B  C  G  H  L  P  T
  A  B  C  D  H  L  P  T
# Ruby Program
# Print all possible paths from top left to bottom right of matrix
class MyMatrix 
	# Define the accessor and reader of class MyMatrix
    attr_reader :rows, :cols
    attr_accessor :rows, :cols
	def initialize(matrix) 
		 # Get the size of matrix
		@rows = matrix.length
		@cols = matrix[0].length
	end
	 # Display of all path of top to bottom and left to right
	def show_path(matrix, result, row, col, count, k) 
		if (row >= self.rows || col >= self.cols) 
			return
		end
		result[count] = matrix[row][col]
		 # recursive execute method with new parameters
		self.show_path(matrix, result, row + 1, col, count + 1, k)
		self.show_path(matrix, result, row, col + 1, count + 1, k)
		if (count + 1 == k) 
			i = 0
			 # Display the result value
			while (i < k) 
				print("  ", result[i])
				i += 1
			end
			print("\n")
		end
	end
end
def main() 
	matrix = [
		['A', 'B', 'C', 'D'],
		['E', 'F', 'G', 'H'],
		['I', 'J', 'K', 'L'],
		['M', 'N', 'O', 'P'],
		['Q', 'R', 'S', 'T']
	]
	obj = MyMatrix.new(matrix)
	 # Auxiliary memory which are storing path result
	result = Array.new(obj.rows + obj.cols - 1, ' ' )
	obj.show_path(matrix, result, 0, 0, 0, obj.rows + obj.cols - 1)
end


main()

Output

  A  E  I  M  Q  R  S  T
  A  E  I  M  N  R  S  T
  A  E  I  M  N  O  S  T
  A  E  I  M  N  O  P  T
  A  E  I  J  N  R  S  T
  A  E  I  J  N  O  S  T
  A  E  I  J  N  O  P  T
  A  E  I  J  K  O  S  T
  A  E  I  J  K  O  P  T
  A  E  I  J  K  L  P  T
  A  E  F  J  N  R  S  T
  A  E  F  J  N  O  S  T
  A  E  F  J  N  O  P  T
  A  E  F  J  K  O  S  T
  A  E  F  J  K  O  P  T
  A  E  F  J  K  L  P  T
  A  E  F  G  K  O  S  T
  A  E  F  G  K  O  P  T
  A  E  F  G  K  L  P  T
  A  E  F  G  H  L  P  T
  A  B  F  J  N  R  S  T
  A  B  F  J  N  O  S  T
  A  B  F  J  N  O  P  T
  A  B  F  J  K  O  S  T
  A  B  F  J  K  O  P  T
  A  B  F  J  K  L  P  T
  A  B  F  G  K  O  S  T
  A  B  F  G  K  O  P  T
  A  B  F  G  K  L  P  T
  A  B  F  G  H  L  P  T
  A  B  C  G  K  O  S  T
  A  B  C  G  K  O  P  T
  A  B  C  G  K  L  P  T
  A  B  C  G  H  L  P  T
  A  B  C  D  H  L  P  T

<?php
/*
  Php Program
  Print all possible paths from top left to bottom right of matrix
*/
class MyMatrix {
	public $rows;
	public $cols;

	function __construct($matrix) {
		//Get the size of matrix
		$this->rows = count($matrix);
		$this->cols = count($matrix[0]);
	}
	//Display of all path of top to bottom and left to right
	function show_path($matrix, &$result, $row, $col, $count, $k) {
		if ($row >= $this->rows || $col >= $this->cols) {
			return;
		}
		$result[$count] = $matrix[$row][$col];
		//recursive execute method with new parameters
		$this->show_path($matrix, $result, $row + 1, $col, $count + 1, $k);
		$this->show_path($matrix, $result, $row, $col + 1, $count + 1, $k);
		if ($count + 1 == $k) {
			//Display the result value

			for ($i = 0; $i < $k; ++$i) {
				echo("  ". $result[$i]);
			}
			echo("\n");
		}
	}
}

function main() {
	$matrix = array(
      array('A', 'B', 'C', 'D'), 
      array('E', 'F', 'G', 'H'), 
      array('I', 'J', 'K', 'L'), 
      array('M', 'N', 'O', 'P'), 
      array('Q', 'R', 'S', 'T')
    );
	$obj = new MyMatrix($matrix);
	//Auxiliary memory which are storing path result
	$result = array_fill(0, $obj->rows + $obj->cols - 1," " );
	$obj->show_path($matrix, $result, 0, 0, 0, $obj->rows + $obj->cols - 1);

}
main();

Output

  A  E  I  M  Q  R  S  T
  A  E  I  M  N  R  S  T
  A  E  I  M  N  O  S  T
  A  E  I  M  N  O  P  T
  A  E  I  J  N  R  S  T
  A  E  I  J  N  O  S  T
  A  E  I  J  N  O  P  T
  A  E  I  J  K  O  S  T
  A  E  I  J  K  O  P  T
  A  E  I  J  K  L  P  T
  A  E  F  J  N  R  S  T
  A  E  F  J  N  O  S  T
  A  E  F  J  N  O  P  T
  A  E  F  J  K  O  S  T
  A  E  F  J  K  O  P  T
  A  E  F  J  K  L  P  T
  A  E  F  G  K  O  S  T
  A  E  F  G  K  O  P  T
  A  E  F  G  K  L  P  T
  A  E  F  G  H  L  P  T
  A  B  F  J  N  R  S  T
  A  B  F  J  N  O  S  T
  A  B  F  J  N  O  P  T
  A  B  F  J  K  O  S  T
  A  B  F  J  K  O  P  T
  A  B  F  J  K  L  P  T
  A  B  F  G  K  O  S  T
  A  B  F  G  K  O  P  T
  A  B  F  G  K  L  P  T
  A  B  F  G  H  L  P  T
  A  B  C  G  K  O  S  T
  A  B  C  G  K  O  P  T
  A  B  C  G  K  L  P  T
  A  B  C  G  H  L  P  T
  A  B  C  D  H  L  P  T
/*
  Scala Program
  Print all possible paths from top left to bottom right of matrix
*/
class MyMatrix(var rows: Int,
	var cols: Int) {
	

	def this(matrix: Array[Array[Char]]) {
		//Get the size of matrix
		this(matrix.length, matrix(0).length);
	}
	//Display of all path of top to bottom and left to right
	def show_path(matrix: Array[Array[Char]], result: Array[Char], row: Int, col: Int, count: Int, k: Int): Unit = {
		if (row >= this.rows || col >= this.cols) {
			return;
		}
		result(count) = matrix(row)(col);

		//recursive execute method with new parameters
		this.show_path(matrix, result, row + 1, col, count + 1, k);
		this.show_path(matrix, result, row, col + 1, count + 1, k);

		if (count + 1 == k) {
			var i: Int = 0;

			//Display the result value
			while (i < k) {
				print("  " + result(i));
				i += 1;
			}
			print("\n");
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val matrix: Array[Array[Char]] = Array(
			Array('A', 'B', 'C', 'D'),
			Array('E', 'F', 'G', 'H'),
			Array('I', 'J', 'K', 'L'),
			Array('M', 'N', 'O', 'P'),
			Array('Q', 'R', 'S', 'T'));
		val obj: MyMatrix = new MyMatrix(matrix);

		//Auxiliary memory which are storing path result
		var result: Array[Char] = Array.fill[Char](obj.rows + obj.cols - 1)(' ');
		obj.show_path(matrix, result, 0, 0, 0, obj.rows + obj.cols - 1);
	}
}

Output

  A  E  I  M  Q  R  S  T
  A  E  I  M  N  R  S  T
  A  E  I  M  N  O  S  T
  A  E  I  M  N  O  P  T
  A  E  I  J  N  R  S  T
  A  E  I  J  N  O  S  T
  A  E  I  J  N  O  P  T
  A  E  I  J  K  O  S  T
  A  E  I  J  K  O  P  T
  A  E  I  J  K  L  P  T
  A  E  F  J  N  R  S  T
  A  E  F  J  N  O  S  T
  A  E  F  J  N  O  P  T
  A  E  F  J  K  O  S  T
  A  E  F  J  K  O  P  T
  A  E  F  J  K  L  P  T
  A  E  F  G  K  O  S  T
  A  E  F  G  K  O  P  T
  A  E  F  G  K  L  P  T
  A  E  F  G  H  L  P  T
  A  B  F  J  N  R  S  T
  A  B  F  J  N  O  S  T
  A  B  F  J  N  O  P  T
  A  B  F  J  K  O  S  T
  A  B  F  J  K  O  P  T
  A  B  F  J  K  L  P  T
  A  B  F  G  K  O  S  T
  A  B  F  G  K  O  P  T
  A  B  F  G  K  L  P  T
  A  B  F  G  H  L  P  T
  A  B  C  G  K  O  S  T
  A  B  C  G  K  O  P  T
  A  B  C  G  K  L  P  T
  A  B  C  G  H  L  P  T
  A  B  C  D  H  L  P  T
/*
  Swift Program
  Print all possible paths from top left to bottom right of matrix
*/
class MyMatrix {
	var rows: Int;
	var cols: Int;
	init(_ matrix: [[Character]]) {
		//Get the size of matrix
		self.rows = matrix.count;
		self.cols = matrix[0].count;
	}
	//Display of all path of top to bottom and left to right
	func show_path(_ matrix: [[Character]], _ result: inout [Character], _ row: Int, _ col: Int, _ count: Int, _ k: Int) {
		if (row >= self.rows || col >= self.cols) {
			return;
		}
		result[count] = matrix[row][col];
		//recursive execute method with new parameters
		self.show_path(matrix, &result, row + 1, col, count + 1, k);
		self.show_path(matrix, &result, row, col + 1, count + 1, k);
		if (count + 1 == k) {
			var i: Int = 0;
			//Display the result value
			while (i < k) {
				print("  ", result[i], terminator: "");
				i += 1;
			}
			print("\n", terminator: "");
		}
	}
}
func main() {
	let matrix: [
		[Character]
	] = [
		["A", "B", "C", "D"],
		["E", "F", "G", "H"],
		["I", "J", "K", "L"],
		["M", "N", "O", "P"],
		["Q", "R", "S", "T"]
	];
	let obj: MyMatrix = MyMatrix(matrix);
	//Auxiliary memory which are storing path result
	var result: [Character] = Array(repeating:" " , count: obj.rows + obj.cols - 1);
	obj.show_path(matrix, &result, 0, 0, 0, obj.rows + obj.cols - 1);
}
main();

Output

   A   E   I   M   Q   R   S   T
   A   E   I   M   N   R   S   T
   A   E   I   M   N   O   S   T
   A   E   I   M   N   O   P   T
   A   E   I   J   N   R   S   T
   A   E   I   J   N   O   S   T
   A   E   I   J   N   O   P   T
   A   E   I   J   K   O   S   T
   A   E   I   J   K   O   P   T
   A   E   I   J   K   L   P   T
   A   E   F   J   N   R   S   T
   A   E   F   J   N   O   S   T
   A   E   F   J   N   O   P   T
   A   E   F   J   K   O   S   T
   A   E   F   J   K   O   P   T
   A   E   F   J   K   L   P   T
   A   E   F   G   K   O   S   T
   A   E   F   G   K   O   P   T
   A   E   F   G   K   L   P   T
   A   E   F   G   H   L   P   T
   A   B   F   J   N   R   S   T
   A   B   F   J   N   O   S   T
   A   B   F   J   N   O   P   T
   A   B   F   J   K   O   S   T
   A   B   F   J   K   O   P   T
   A   B   F   J   K   L   P   T
   A   B   F   G   K   O   S   T
   A   B   F   G   K   O   P   T
   A   B   F   G   K   L   P   T
   A   B   F   G   H   L   P   T
   A   B   C   G   K   O   S   T
   A   B   C   G   K   O   P   T
   A   B   C   G   K   L   P   T
   A   B   C   G   H   L   P   T
   A   B   C   D   H   L   P   T
/*
  Node Js Program
  Print all possible paths from top left to bottom right of matrix
*/
class MyMatrix {
	
	constructor(matrix) {
		//Get the size of matrix
		this.rows = matrix.length;
		this.cols = matrix[0].length;
	}

	//Display of all path of top to bottom and left to right
	show_path(matrix, result, row, col, count, k) {
		if (row >= this.rows || col >= this.cols) {
			return;
		}
		result[count] = matrix[row][col];
		//recursive execute method with new parameters
		this.show_path(matrix, result, row + 1, col, count + 1, k);
		this.show_path(matrix, result, row, col + 1, count + 1, k);
		if (count + 1 == k) {
			var i = 0;
			//Display the result value
			while (i < k) {
				process.stdout.write("  " + result[i]);
				i++;
			}

			process.stdout.write("\n");
		}
	}
}

function main(args) {
	var matrix = [
		['A', 'B', 'C', 'D'],
		['E', 'F', 'G', 'H'],
		['I', 'J', 'K', 'L'],
		['M', 'N', 'O', 'P'],
		['Q', 'R', 'S', 'T']
	];
	var obj = new MyMatrix(matrix);
	//Auxiliary memory which are storing path result
	var result = Array(obj.rows + obj.cols - 1).fill(' ');
	obj.show_path(matrix, result, 0, 0, 0, obj.rows + obj.cols - 1);
}

main();

Output

  A  E  I  M  Q  R  S  T
  A  E  I  M  N  R  S  T
  A  E  I  M  N  O  S  T
  A  E  I  M  N  O  P  T
  A  E  I  J  N  R  S  T
  A  E  I  J  N  O  S  T
  A  E  I  J  N  O  P  T
  A  E  I  J  K  O  S  T
  A  E  I  J  K  O  P  T
  A  E  I  J  K  L  P  T
  A  E  F  J  N  R  S  T
  A  E  F  J  N  O  S  T
  A  E  F  J  N  O  P  T
  A  E  F  J  K  O  S  T
  A  E  F  J  K  O  P  T
  A  E  F  J  K  L  P  T
  A  E  F  G  K  O  S  T
  A  E  F  G  K  O  P  T
  A  E  F  G  K  L  P  T
  A  E  F  G  H  L  P  T
  A  B  F  J  N  R  S  T
  A  B  F  J  N  O  S  T
  A  B  F  J  N  O  P  T
  A  B  F  J  K  O  S  T
  A  B  F  J  K  O  P  T
  A  B  F  J  K  L  P  T
  A  B  F  G  K  O  S  T
  A  B  F  G  K  O  P  T
  A  B  F  G  K  L  P  T
  A  B  F  G  H  L  P  T
  A  B  C  G  K  O  S  T
  A  B  C  G  K  O  P  T
  A  B  C  G  K  L  P  T
  A  B  C  G  H  L  P  T
  A  B  C  D  H  L  P  T

Time Complexity Analysis

In the worst case, the algorithm explores all paths from the top-left to the bottom-right corner of the matrix. Since there are 2^(R+C-2) possible paths, the time complexity is exponential, O(2^(R+C-2)).

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post