dmilicev

matrix_connected_path_v1.c

May 8th, 2020
205
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.67 KB | None
  1. /*
  2.  
  3.     matrix_connected_path_v1.c
  4.  
  5.     Task:
  6.     https://web.facebook.com/groups/c.programing/1574287172730127/
  7.  
  8.     Function connected_path() checks if 1s are on the connected path.
  9.  
  10.  
  11.     You can find all my C programs at Dragan Milicev's pastebin:
  12.  
  13.     https://pastebin.com/u/dmilicev
  14.  
  15. */
  16.  
  17. #include <stdio.h>
  18.  
  19. #define MAX_SIZE 20
  20.  
  21. // Displays a square matrix M[n][n] that has integers in n rows and n columns
  22. void display_square_matrix( char *text, int M[][MAX_SIZE], int n )
  23. {
  24.     int i, j;
  25.  
  26.     printf("\n%s\n\n",text);
  27.  
  28.     for(i=0; i<n; i++)                      // print matrix M[n][n]
  29.     {
  30.         for(j=0; j<n; j++)
  31.             printf("%3d", M[i][j]);
  32.  
  33.         printf("\n\n");                     // new row of matrix
  34.     }
  35. }
  36.  
  37.  
  38. // return 1 if ones (1s) are in connected path, otherwise return 0
  39. int connected_path( int M[][MAX_SIZE], int n, int r, int c )
  40. {
  41.     if( M[r][c]==1 && r>=0 && r<n && c>=0 && c<n )  // limits
  42.     {
  43.         M[r][c]=0;
  44.  
  45.         // remove this two comments if you want to see how it works
  46.         //printf("\n M[%d][%d] = %d \n", r, c, M[r][c] );
  47.         //display_square_matrix("", M, n);
  48.  
  49.         connected_path(M, n, r+1, c);       // down
  50.         connected_path(M, n, r-1, c);       // up
  51.         connected_path(M, n, r, c+1);       // right
  52.         connected_path(M, n, r, c-1);       // left
  53.     }
  54.  
  55.     for(r=0; r<n; r++)                      // find 1
  56.     {
  57.         for(c=0; c<n; c++)
  58.             if( M[r][c]== 1 )
  59.                 return 0;                   // 1 was found
  60.     }
  61.  
  62.     return 1;                               // 1 not found
  63. } //connected_path()
  64.  
  65.  
  66. int main(void)
  67. {
  68.     int n=10;   // don't forget to put n=4 for other examples
  69. /*
  70.     int M[MAX_SIZE][MAX_SIZE] = {
  71.                                     { 1,1,1,1 },
  72.                                     { 1,1,1,1 },
  73.                                     { 1,1,1,1 },
  74.                                     { 1,1,1,1 }
  75.                                 };
  76. */
  77. /*
  78.     int M[MAX_SIZE][MAX_SIZE] = {
  79.                                     { 1,0,1,1 },
  80.                                     { 1,0,1,1 },
  81.                                     { 1,0,0,0 },
  82.                                     { 1,1,1,1 }
  83.                                 };
  84. */
  85. /*
  86.     int M[MAX_SIZE][MAX_SIZE] = {
  87.                                     { 1,0,1,1 },
  88.                                     { 1,0,0,0 },
  89.                                     { 1,0,0,1 },
  90.                                     { 1,1,1,1 }
  91.                                 };
  92. */
  93.  
  94.     int M[MAX_SIZE][MAX_SIZE] = {
  95.                                     { 1,1,1,0,1,1,1,1,1,1 },
  96.                                     { 1,1,1,0,0,0,1,1,1,1 },
  97.                                     { 1,1,1,1,1,0,1,1,1,1 },
  98.                                     { 1,1,1,1,1,0,1,1,1,1 },
  99.                                     { 1,1,1,1,1,0,0,0,0,0 },
  100.                                     { 1,1,1,1,1,1,1,1,1,1 },
  101.                                     { 1,1,1,1,1,1,1,1,1,1 },
  102.                                     { 1,1,1,1,1,1,1,1,1,1 },
  103.                                     { 1,1,1,1,1,1,1,1,1,1 },
  104.                                     { 1,1,1,1,1,1,1,1,1,1 }
  105.                                 };
  106.  
  107.  
  108.  
  109.     printf("\n --------------------------------- \n");
  110.  
  111.     display_square_matrix("\n Connected path ? \n", M, n);
  112.  
  113.     if( connected_path(M, n, 0, 0) )
  114.         display_square_matrix("\n YES, because \n", M, n);
  115.     else
  116.         display_square_matrix("\n NO, because \n", M, n);
  117.  
  118.     printf("\n --------------------------------- \n");
  119.  
  120.  
  121.     return 0;
  122.  
  123. } // main()
RAW Paste Data Copied