Count the number of ways to traverse a Matrix
The problem involves counting the number of ways to traverse a matrix from the top-left corner to the bottom-right corner. The matrix has rows and columns, and we can only move down or right at each step. The goal is to find the total number of unique paths that can be taken to reach the bottom-right corner.
Problem Statement
Given a matrix with rows and columns, the task is to count the number of ways to traverse the matrix from the top-left corner to the bottom-right corner, only moving down or right.
Example Scenario
Consider a matrix with 9 rows and 7 columns. We want to count the number of unique paths to traverse this matrix. The result is 3003.
Idea to Solve the Problem
To solve this problem, we can use a recursive approach. At each step, we have two choices: either move down or move right. We recursively calculate the number of paths by summing up the number of paths from the cell below and the cell to the right.
Pseudocode
int countPath(int i, int j, int row, int col)
{
if (i == row && col == j)
return 1;
else if (i <= row && j <= col)
return countPath(i + 1, j, row, col) + countPath(i, j + 1, row, col);
else
return 0;
}
Algorithm Explanation
- Implement a function
countPath
that takes four arguments:i
(current row),j
(current column),row
(total number of rows), andcol
(total number of columns). - Implement base cases:
- If
i
reaches the last row andj
reaches the last column, return 1 (we reached the bottom-right corner). - If both
i
andj
are within the matrix bounds, recursively calculate the number of paths from the cell below (i + 1
) and the cell to the right (j + 1
). - If we go out of bounds, return 0.
- If
- The recursive cases involve adding the number of paths from the cell below and the cell to the right.
Code Solution
// C Program
// Count the number of ways to traverse a Matrix
#include <stdio.h>
// Count matrix path
int countPath(int i, int j, int row, int col)
{
if (i == row && col == j)
{
return 1;
}
else if (i <= row && j <= col)
{
// Count matrix path recursively
return countPath(i + 1, j, row, col) + countPath(i, j + 1, row, col);
}
else
{
return 0;
}
}
// Handles the request to count path of the matrix
void paths(int row, int col)
{
if (row <= 0 || col <= 0)
{
return;
}
// Display given rows and columns
printf(" Row : %d, Col : %d", row, col);
// Display calculated result
printf("\n Paths : %d\n\n", countPath(0, 0, row - 1, col - 1));
}
int main()
{
// Test Cases
paths(9, 7);
paths(3, 7);
paths(4, 4);
return 0;
}
input
Row : 9, Col : 7
Paths : 3003
Row : 3, Col : 7
Paths : 28
Row : 4, Col : 4
Paths : 20
/*
Java Program
Count the number of ways to traverse a Matrix
*/
public class Counting
{
// Count matrix path
public int countPath(int i, int j, int row, int col)
{
if (i == row && col == j)
{
return 1;
}
else if (i <= row && j <= col)
{
// Count matrix path recursively
return countPath(i + 1, j, row, col) +
countPath(i, j + 1, row, col);
}
else
{
return 0;
}
}
// Handles the request to count path of the matrix
public void paths(int row, int col)
{
if (row <= 0 || col <= 0)
{
return;
}
// Display given rows and columns
System.out.print(" Row : " + row + ", Col : " + col );
// Display calculated result
System.out.print("\n Paths : " +
countPath(0, 0, row - 1, col - 1) + "\n\n");
}
public static void main(String[] args)
{
Counting task = new Counting();
// Test Cases
task.paths(9, 7);
task.paths(3, 7);
task.paths(4, 4);
}
}
input
Row : 9, Col : 7
Paths : 3003
Row : 3, Col : 7
Paths : 28
Row : 4, Col : 4
Paths : 20
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Count the number of ways to traverse a Matrix
*/
class Counting
{
public:
// Count matrix path
int countPath(int i, int j, int row, int col)
{
if (i == row && col == j)
{
return 1;
}
else if (i <= row && j <= col)
{
// Count matrix path recursively
return this->countPath(i + 1, j, row, col)
+ this->countPath(i, j + 1, row, col);
}
else
{
return 0;
}
}
// Handles the request to count path of the matrix
void paths(int row, int col)
{
if (row <= 0 || col <= 0)
{
return;
}
// Display given rows and columns
cout << " Row : " << row << ", Col : " << col;
// Display calculated result
cout << "\n Paths : " << this->countPath(0, 0, row - 1, col - 1)
<< "\n\n";
}
};
int main()
{
Counting *task = new Counting();
// Test Cases
task->paths(9, 7);
task->paths(3, 7);
task->paths(4, 4);
return 0;
}
input
Row : 9, Col : 7
Paths : 3003
Row : 3, Col : 7
Paths : 28
Row : 4, Col : 4
Paths : 20
// Include namespace system
using System;
/*
Csharp Program
Count the number of ways to traverse a Matrix
*/
public class Counting
{
// Count matrix path
public int countPath(int i, int j, int row, int col)
{
if (i == row && col == j)
{
return 1;
}
else if (i <= row && j <= col)
{
// Count matrix path recursively
return this.countPath(i + 1, j, row, col) +
this.countPath(i, j + 1, row, col);
}
else
{
return 0;
}
}
// Handles the request to count path of the matrix
public void paths(int row, int col)
{
if (row <= 0 || col <= 0)
{
return;
}
// Display given rows and columns
Console.Write(" Row : " + row + ", Col : " + col);
// Display calculated result
Console.WriteLine("\n Paths : " + this.countPath(0, 0, row - 1, col - 1) + "\n");
}
public static void Main(String[] args)
{
Counting task = new Counting();
// Test Cases
task.paths(9, 7);
task.paths(3, 7);
task.paths(4, 4);
}
}
input
Row : 9, Col : 7
Paths : 3003
Row : 3, Col : 7
Paths : 28
Row : 4, Col : 4
Paths : 20
<?php
/*
Php Program
Count the number of ways to traverse a Matrix
*/
class Counting
{
// Count matrix path
public function countPath($i, $j, $row, $col)
{
if ($i == $row && $col == $j)
{
return 1;
}
else if ($i <= $row && $j <= $col)
{
// Count matrix path recursively
return $this->countPath($i + 1, $j, $row, $col)
+ $this->countPath($i, $j + 1, $row, $col);
}
else
{
return 0;
}
}
// Handles the request to count path of the matrix
public function paths($row, $col)
{
if ($row <= 0 || $col <= 0)
{
return;
}
// Display given rows and columns
echo(" Row : ".$row.
", Col : ".$col);
// Display calculated result
echo("\n Paths : ".$this->countPath(0, 0, $row - 1, $col - 1).
"\n\n");
}
}
function main()
{
$task = new Counting();
// Test Cases
$task->paths(9, 7);
$task->paths(3, 7);
$task->paths(4, 4);
}
main();
input
Row : 9, Col : 7
Paths : 3003
Row : 3, Col : 7
Paths : 28
Row : 4, Col : 4
Paths : 20
/*
Node JS Program
Count the number of ways to traverse a Matrix
*/
class Counting
{
// Count matrix path
countPath(i, j, row, col)
{
if (i == row && col == j)
{
return 1;
}
else if (i <= row && j <= col)
{
// Count matrix path recursively
return this.countPath(i + 1, j, row, col)
+ this.countPath(i, j + 1, row, col);
}
else
{
return 0;
}
}
// Handles the request to count path of the matrix
paths(row, col)
{
if (row <= 0 || col <= 0)
{
return;
}
// Display given rows and columns
process.stdout.write(" Row : " + row + ", Col : " + col);
// Display calculated result
console.log("\n Paths : "
+ this.countPath(0, 0, row - 1, col - 1)
+ "\n");
}
}
function main()
{
var task = new Counting();
// Test Cases
task.paths(9, 7);
task.paths(3, 7);
task.paths(4, 4);
}
main();
input
Row : 9, Col : 7
Paths : 3003
Row : 3, Col : 7
Paths : 28
Row : 4, Col : 4
Paths : 20
# Python 3 Program
# Count the number of ways to traverse a Matrix
class Counting :
# Count matrix path
def countPath(self, i, j, row, col) :
if (i == row and col == j) :
return 1
elif (i <= row and j <= col) :
# Count matrix path recursively
return self.countPath(
i + 1, j, row, col
) + self.countPath(
i, j + 1, row, col
)
else :
return 0
# Handles the request to count path of the matrix
def paths(self, row, col) :
if (row <= 0 or col <= 0) :
return
# Display given rows and columns
print(" Row : ", row ,", Col : ", col, end = "")
# Display calculated result
print("\n Paths : ", self.countPath(0, 0, row - 1, col - 1) ,"\n")
def main() :
task = Counting()
# Test Cases
task.paths(9, 7)
task.paths(3, 7)
task.paths(4, 4)
if __name__ == "__main__": main()
input
Row : 9 , Col : 7
Paths : 3003
Row : 3 , Col : 7
Paths : 28
Row : 4 , Col : 4
Paths : 20
# Ruby Program
# Count the number of ways to traverse a Matrix
class Counting
# Count matrix path
def countPath(i, j, row, col)
if (i == row && col == j)
return 1
elsif (i <= row && j <= col)
# Count matrix path recursively
return self.countPath(i + 1, j, row, col) +
self.countPath(i, j + 1, row, col)
else
return 0
end
end
# Handles the request to count path of the matrix
def paths(row, col)
if (row <= 0 || col <= 0)
return
end
# Display given rows and columns
print(" Row : ", row ,", Col : ", col)
# Display calculated result
print("\n Paths : ",
self.countPath(0, 0, row - 1, col - 1) ,
"\n\n")
end
end
def main()
task = Counting.new()
# Test Cases
task.paths(9, 7)
task.paths(3, 7)
task.paths(4, 4)
end
main()
input
Row : 9, Col : 7
Paths : 3003
Row : 3, Col : 7
Paths : 28
Row : 4, Col : 4
Paths : 20
/*
Scala Program
Count the number of ways to traverse a Matrix
*/
class Counting()
{
// Count matrix path
def countPath(i: Int, j: Int, row: Int, col: Int): Int = {
if (i == row && col == j)
{
return 1;
}
else if (i <= row && j <= col)
{
// Count matrix path recursively
return countPath(i + 1, j, row, col) +
countPath(i, j + 1, row, col);
}
else
{
return 0;
}
}
// Handles the request to count path of the matrix
def paths(row: Int, col: Int): Unit = {
if (row <= 0 || col <= 0)
{
return;
}
// Display given rows and columns
print(" Row : " + row + ", Col : " + col);
// Display calculated result
print("\n Paths : " + countPath(0, 0, row - 1, col - 1) + "\n\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Counting = new Counting();
// Test Cases
task.paths(9, 7);
task.paths(3, 7);
task.paths(4, 4);
}
}
input
Row : 9, Col : 7
Paths : 3003
Row : 3, Col : 7
Paths : 28
Row : 4, Col : 4
Paths : 20
/*
Swift 4 Program
Count the number of ways to traverse a Matrix
*/
class Counting
{
// Count matrix path
func countPath(_ i: Int, _ j: Int, _ row: Int, _ col: Int) -> Int
{
if (i == row && col == j)
{
return 1;
}
else if (i <= row && j <= col)
{
// Count matrix path recursively
return self.countPath(i + 1, j, row, col) +
self.countPath(i, j + 1, row, col);
}
else
{
return 0;
}
}
// Handles the request to count path of the matrix
func paths(_ row: Int, _ col: Int)
{
if (row <= 0 || col <= 0)
{
return;
}
// Display given rows and columns
print(" Row : ", row ,", Col : ", col, terminator: "");
// Display calculated result
print("\n Paths : ", self.countPath(0, 0, row - 1, col - 1) ,"\n");
}
}
func main()
{
let task = Counting();
// Test Cases
task.paths(9, 7);
task.paths(3, 7);
task.paths(4, 4);
}
main();
input
Row : 9 , Col : 7
Paths : 3003
Row : 3 , Col : 7
Paths : 28
Row : 4 , Col : 4
Paths : 20
/*
Kotlin Program
Count the number of ways to traverse a Matrix
*/
class Counting
{
// Count matrix path
fun countPath(i: Int, j: Int, row: Int, col: Int): Int
{
if (i == row && col == j)
{
return 1;
}
else if (i <= row && j <= col)
{
// Count matrix path recursively
return this.countPath(i + 1, j, row, col) +
this.countPath(i, j + 1, row, col);
}
else
{
return 0;
}
}
// Handles the request to count path of the matrix
fun paths(row: Int, col: Int): Unit
{
if (row <= 0 || col <= 0)
{
return;
}
// Display given rows and columns
print(" Row : " + row + ", Col : " + col);
// Display calculated result
print("\n Paths : " + this.countPath(0, 0, row - 1, col - 1) + "\n\n");
}
}
fun main(args: Array < String > ): Unit
{
val task: Counting = Counting();
// Test Cases
task.paths(9, 7);
task.paths(3, 7);
task.paths(4, 4);
}
input
Row : 9, Col : 7
Paths : 3003
Row : 3, Col : 7
Paths : 28
Row : 4, Col : 4
Paths : 20
Output Explanation
The code implements the algorithm and finds the number of unique paths to traverse a matrix based on the provided input. It demonstrates three test cases and displays the resulting number of paths.
Time Complexity
The time complexity of this algorithm is O(2^(m + n)), where m
is the number of rows and n
is the number of columns in the matrix. This is because for each cell, we consider two choices: moving down or
moving right. The recursion tree can have up to 2^(m + n) nodes. While this approach works for small matrices, it
becomes inefficient for larger ones. Dynamic programming can be used to optimize the solution.
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