count_all_possible_paths_in_matrix.c

/*

    count_all_possible_paths_in_matrix.c

Count all possible paths from top left to bottom right of a r x c matrix.

https://www.w3resource.com/c-programming-exercises/array/c-array-exercise-85.php

First, we set the matrix elements in the first column and first row to 1.
Each internal element of the matrix can be reached from the top or from the left.
That's why for each internal element we write the sum of its upper and its left element.
Then the sum of all possible paths from top left to bottom right element is
in the bottom right element.

    You can find all my C programs at Dragan Milicev's pastebin:

    https://pastebin.com/u/dmilicev

*/

#include <stdio.h>

#define MAX_SIZE 100    // maximum size of matrix M[100][100]

// Displays a matrix M[rows][columns] of integers with text before and after the matrix
void PrintMatrix(char *text_before, int M[][MAX_SIZE], int rows, int columns, char *text_after){
    printf("%s", text_before);
    for(int r=0;r<rows;r++){
        for(int c=0;c<columns;c++)
            printf("%3d",M[r][c]);
        printf("\n\n");
    }
    printf("%s", text_after);
}

// Displays a matrix M[rows][columns] of integers
void DisplayMatrix(int M[][MAX_SIZE], int rows, int columns){
    for (int r = 0; r < rows; r++){
        for (int c = 0; c < columns; c++)
            printf("%3d",M[r][c]);
        printf("\n\n");
    }
}

int PathCounting(int r, int c){
    int M[MAX_SIZE][MAX_SIZE];

// First, we set the matrix elements in the first column and first row to 1.
    printf("\n Assign the value 1 to the elements of the first column: \n");
    printf("\n begin M[i][0] = 1; \n\n");
    for (int i = 0; i < r; i++){
        M[i][0] = 1;
        printf("\t * i=%d , j=0, M[%d][0] = %d \n", i, i, M[i][0]);
        PrintMatrix("\n",M,r,c,"\n");
    }
    printf(" end M[i][0] = 1; \n");

    printf("\n Assign the value 1 to the elements of the first row: \n");
    printf("\n begin M[0][j] = 1; \n\n");
    for (int j = 0; j < c; j++){
        M[0][j] = 1;
        printf("\t * i=0 , j=%d, M[0][%d] = %d \n", j, j, M[0][j]);
        PrintMatrix("\n",M,r,c,"\n");
    }
    printf(" end M[0][j] = 1; \n");

// Each internal element of the matrix can be reached from the top or from the left.
// That's why for each internal element we write the sum of its upper and its left element.
    printf("\n Assign the values to the inner elements: \n");
    printf("\n begin M[i][j] = M[i-1][j] + M[i][j-1]; \n\n");
    for (int i = 1; i < r; i++)
        for (int j = 1; j < c; j++){
            M[i][j] = M[i-1][j] + M[i][j-1];

            printf("\t * i=%d , j=%d, M[%d][%d] = M[%d-1][%d] + M[%d][%d-1] = \n\t\t\t        M[%3d][%d] + M[%d][%3d] = %d + %d = %d \n",
                    i, j, i, j, i, j, i, j,  i-1, j,  i, j-1,  M[i-1][j], M[i][j-1], M[i][j]);

            PrintMatrix("\n",M,r,c,"\n");
        }
    printf(" end M[i][j] = M[i-1][j] + M[i][j-1]; \n");

// Then the sum of all possible paths from top left to bottom right element is
// in the bottom right element.
    return M[r-1][c-1];
}

int main(void)
{
    int r=4, c=4;   // Matrix of 4 rows and 4 columns.

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

    return 0;
}