 # matrix_max_sum__path.c

Nov 17th, 2019
287
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2.
3.     matrix_max_sum__path.c
4.
8.
9.
10.     You can find all my C programs at Dragan Milicev's pastebin:
11.
12.     https://pastebin.com/u/dmilicev
13.
14. */
15.
16.
17. #include <stdio.h>
18.
19. #define ROWS 4
20. #define COLUMNS 3
21.
22. typedef int TMATRIX[ROWS][COLUMNS];
23.
24.
25. // Displays a matrix M [] [] that has r rows and c columns
26. void display_matrix( char *text, TMATRIX M, int r, int c )
27. {
28.     int i, j;
29.
30.     printf("\n%s\n\n",text);
31.
32.     for(i=0;i<r;i++) {                  // print matrix M[][]
33.         for(j=0;j<c;j++)
34.             printf(" %4d", M[i][j]);
35.
36.         printf("\n\n");                 // new row of matrix
37.     }
38. }
39.
40.
41.
42. int main(void)
43. {
44.     int r=0, c=0, end=0;    // current row and column in matrix M[r][c]
45.     TMATRIX M = {
46.                    { 9, 9, 7 },
47.                    { 9, 7, 2 },
48.                    { 6, 9, 5 },
49.                    { 9, 1, 2 }
50.                 };
51.
52.     display_matrix("\n Matrix M is: \n", M, ROWS, COLUMNS);
53.
54. /*
55.     When moving through the matrix in the down or right direction,
56.     4 cases are possible:
57.     1. we can go down or right then go where it is larger number
58.     2. we cannot go down but we can go right and then go right
59.     3. we cannot go right but we can down and then we go down
60.     4. we can't go down or right and that's when the movement is over.
61. */
62.
63.     printf("\n\n M[%d][%d] = %3d", r, c, M[r][c] ); // print the starting element of the matrix
64.
65.     while( !end )
66.     {
67.         if( r<ROWS-1 && c<COLUMNS-1 )       // 1. case, we can go down or right
68.         {
69.             if( M[r+1][c] >= M[r][c+1] )    // go down
70.             {
71.                 r++;
72.             }
73.             else                            // go right
74.             {
75.                 c++;
76.             }
77.         }
78.         else if( r==ROWS-1 && c<COLUMNS-1 ) // 2. we cannot go down but we can go right
79.         {
80.             c++;                            // go right
81.         }
82.         else if( r<ROWS-1 && c==COLUMNS-1 ) // 3. we cannot go right but we can down
83.         {
84.             r++;                            // go down
85.         }
86.         else if( r==ROWS-1 || c==COLUMNS-1 )// 4. we can't go down or right
87.         {
88.             end=1;                          // end of movement
89.         }
90.
91.         if( !end )
92.             printf("\n M[%d][%d] = %3d", r, c, M[r][c] );   // print that element of the matrix
93.
94.     } // while( !end )
95.
96.
97.     printf("\n\n");
98.
99.     return 0;
100. }