Skip to main content

Count the number of ways to traverse a Matrix

Counting the number of ways to traverse a matrix recursively refers to the process of determining the number of unique paths that can be taken to move from the top-left corner to the bottom-right corner of a matrix, by only moving either right or down at each step.

 Row : 9, Col : 7
 Paths : 3003

To compute the result of counting the number of ways to traverse a matrix with 9 rows and 7 columns, I would need to know if there are any obstacles or blocked cells in the matrix, or if we can freely move through any cell in the matrix.

Assuming that there are no obstacles or blocked cells, and we can freely move through any cell in the matrix, I can use the recursive approach I described earlier to compute the result:

Starting from the top-left corner, we can move either right or down to reach the next cell. Since there are no obstacles or blocked cells, we can make this choice at every step. We repeat this process until we reach the bottom-right corner.

Using the recursive approach, the result of counting the number of ways to traverse a matrix with 9 rows and 7 columns without any obstacles is C(9+7-2, 7-1) = C(14, 6) = 3003.

Here, C(n, r) denotes the number of combinations of r items that can be selected from a set of n items, and can be computed using the formula C(n, r) = n! / (r! * (n-r)!), where "!" denotes the factorial function.

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
Last updated on by Kalkicode




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