C Exercises: Count all possible paths from top left to bottom right of a m X n matrix

Last update on March 18 2025 13:23:18 (UTC/GMT +8 hours)

85. Count Paths in m x n Matrix

Write a program in C to count all possible paths from top left to bottom right of a m X n matrix.

Expected Output:
The size of matrix is : 4 x 4
The all possible paths from top left to bottom right is: 20

The task requires writing a C program to calculate the total number of possible paths from the top-left corner to the bottom-right corner in an m x n matrix. The program should utilize combinatorial mathematics or dynamic programming to determine the number of unique paths, considering that only movements to the right or downward are allowed. The output will display the matrix dimensions and the total number of possible paths.

Sample Solution:

C Code:

#include <stdio.h>

// Function to count all possible paths from top-left to bottom-right in a matrix of size m x n
int PathCounting(int m, int n)
{
    int ctr[m][n]; // Define a matrix to store path counts

    // Initialize the leftmost column elements to 1 (only one way to reach each cell in the leftmost column)
    for (int i = 0; i < m; i++)
    {
        ctr[i][0] = 1;
    }

    // Initialize the top row elements to 1 (only one way to reach each cell in the top row)
    for (int j = 0; j < n; j++)
    {
        ctr[0][j] = 1;
    }

    // Calculate the number of paths for each cell in the matrix
    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            ctr[i][j] = ctr[i - 1][j] + ctr[i][j - 1]; // Number of paths to reach current cell = paths from left + paths from top
        }
    }

    return ctr[m - 1][n - 1]; // Return the number of paths to reach the bottom-right cell
}

int main()
{
    int p, q;
    p = 4; // Number of rows in the matrix
    q = 4; // Number of columns in the matrix

    printf("The size of matrix is: %d, %d\n", p, q);
    printf("The all possible paths from top left to bottom right is: %d\n", PathCounting(p, q));

    return 0;
}

Output:

The size of matrix is : 4 x 4
The all possible paths from top left to bottom right is: 20

Visual Presentation:

Flowchart:/p>

For more Practice: Solve these Related Problems:

• Write a C program to count the number of paths from the top-left to bottom-right of an m x n matrix using recursion.
• Write a C program to compute the number of paths using dynamic programming in a grid with obstacles.
• Write a C program to count paths in a matrix using combinatorial mathematics (nCr formula).
• Write a C program to count all possible paths in an m x n matrix using iterative loops.

C Programming Code Editor:

Click to Open Editor

Previous: Write a program in C to find the minimum distance between two numbers in a given array.
Next: Write a program in C to find the equilibrium index of an array.