Advertisement
dmilicev

matrix_max_sum__path.c

Nov 17th, 2019
287
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.16 KB | None
  1. /*
  2.  
  3.     matrix_max_sum__path.c
  4.  
  5.     Task from Emeka Elemuo
  6.     https://web.facebook.com/emeka.elemuo.3
  7.     https://web.facebook.com/photo.php?fbid=10214995335219225&set=p.10214995335219225&type=3&theater
  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. }
Advertisement
RAW Paste Data Copied
Advertisement