matrix_max_sum__path.c

/*

    matrix_max_sum__path.c

    Task from Emeka Elemuo
    https://web.facebook.com/emeka.elemuo.3
    https://web.facebook.com/photo.php?fbid=10214995335219225&set=p.10214995335219225&type=3&theater


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

    https://pastebin.com/u/dmilicev

*/


#include <stdio.h>

#define ROWS 4
#define COLUMNS 3

typedef int TMATRIX[ROWS][COLUMNS];


// Displays a matrix M [] [] that has r rows and c columns
void display_matrix( char *text, TMATRIX M, int r, int c )
{
    int i, j;

    printf("\n%s\n\n",text);

    for(i=0;i<r;i++) {                  // print matrix M[][]
        for(j=0;j<c;j++)
            printf(" %4d", M[i][j]);

        printf("\n\n");                 // new row of matrix
    }
}



int main(void)
{
    int r=0, c=0, end=0;    // current row and column in matrix M[r][c]
    TMATRIX M = {
                   { 9, 9, 7 },
                   { 9, 7, 2 },
                   { 6, 9, 5 },
                   { 9, 1, 2 }
                };

    display_matrix("\n Matrix M is: \n", M, ROWS, COLUMNS);

/*
    When moving through the matrix in the down or right direction,
    4 cases are possible:
    1. we can go down or right then go where it is larger number
    2. we cannot go down but we can go right and then go right
    3. we cannot go right but we can down and then we go down
    4. we can't go down or right and that's when the movement is over.
*/

    printf("\n\n M[%d][%d] = %3d", r, c, M[r][c] ); // print the starting element of the matrix

    while( !end )
    {
        if( r<ROWS-1 && c<COLUMNS-1 )       // 1. case, we can go down or right
        {
            if( M[r+1][c] >= M[r][c+1] )    // go down
            {
                r++;
            }
            else                            // go right
            {
                c++;
            }
        }
        else if( r==ROWS-1 && c<COLUMNS-1 ) // 2. we cannot go down but we can go right
        {
            c++;                            // go right
        }
        else if( r<ROWS-1 && c==COLUMNS-1 ) // 3. we cannot go right but we can down
        {
            r++;                            // go down
        }
        else if( r==ROWS-1 || c==COLUMNS-1 )// 4. we can't go down or right
        {
            end=1;                          // end of movement
        }

        if( !end )
            printf("\n M[%d][%d] = %3d", r, c, M[r][c] );   // print that element of the matrix

    } // while( !end )


    printf("\n\n");

    return 0;
}