matrix_connected_path_v1.c

May 8th, 2020
205
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2.
3.     matrix_connected_path_v1.c
4.
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