/home/toolbox/public_html/solutions/111/11110/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /*
16 * Author: Isaac Traxler
17 * Date: 2019-10-23
18 * Purpose: fun
19 * Problem: 11110
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24 */
25
26 #define MAX_DIM 105
27 #define UNFILLED 0
28 #define FILLED 111
29 #define IGNORE 112
30 #define R 0
31 #define C 1
32 #define NL 10
33 #define MAX_BUFF 1024
34
35 int size;
36 int tbl[MAX_DIM][MAX_DIM];
37 int start[MAX_DIM][2];
38 char buff[1+MAX_BUFF];
39
40 void init()
41 {
42 /* FUNCTION init */
43 int i;
44 int j;
45
46 for (i=0; (1+size)>=i; i++)
47 {
48 /* all of the outside of the matrix */
49 tbl[0][i] = IGNORE;
50 tbl[1+size][i] = IGNORE;
51 tbl[i][0] = IGNORE;
52 tbl[i][1+size] = IGNORE;
53 } /* all of the outside of the matrix */
54 for (i=1; size>=i; i++)
55 {
56 /* for each row */
57 for (j=1; size>=j; j++)
58 {
59 /* for each column */
60 tbl[i][j] = UNFILLED;
61 } /* for each column */
62 } /* for each row */
63 } /* FUNCTION init */
64
65 void dump()
66 {
67 /* FUNCTION dump */
68 int i;
69 int j;
70
71 for (i=0; (1+size)>=i; i++)
72 {
73 /* for each row */
74 for (j=0; (1+size)>=j; j++)
75 {
76 /* for each column */
77 printf("%3d ", tbl[i][j]);
78 } /* for each column */
79 printf("\n");
80 } /* for each row */
81 } /* FUNCTION dump */
82
83 int getInput()
84 {
85 /* FUNCTION getInput */
86 int dataReadFlag = FALSE;
87 int i;
88 int j;
89 int r;
90 int c;
91 int tmp;
92 char chr;
93 char *token;
94
95 fgets(buff, MAX_BUFF, stdin);
96 sscanf(buff, " %d ", &size);
97 DEBUG printf("size is %d\n", size);
98 if (0 < size)
99 {
100 /* We have data to proces */
101 dataReadFlag = TRUE;
102 init();
103 for (i=1; size>i; i++)
104 {
105 /* loop for each partition */
106 r = -1;
107 fgets(buff, MAX_BUFF, stdin);
108 buff[strlen(buff)-1] = 0; /* deal with NL at end of string */
109 DEBUG printf("[%s]\n", buff);
110 token = strtok(buff, " ");
111 while (NULL != token)
112 {
113 /* process pairs of numbers */
114 sscanf(token, " %d ", &r);
115 token = strtok(NULL, " ");
116 sscanf(token, " %d ", &c);
117 token = strtok(NULL, " ");
118 DEBUG printf("partiton: %d (%d, %d)\n", i, r, c);
119 tbl[r][c] = i;
120 start[i][R] = r;
121 start[i][C] = c;
122 } /* process pairs of numbers */
123 if (0 > r)
124 {
125 /* blank line hack */
126 start[i][R] = 0;
127 start[i][C] = 0;
128 } /* blank line hack */
129 } /* loop for each partition */
130 } /* We have data to proces */
131 return (dataReadFlag);
132 } /* FUNCTION getInput */
133
134 void findZero()
135 {
136 /* FUNCTION findZero */
137 int i;
138 int j;
139
140 for (i=1; size>=i; i++)
141 {
142 /* for each row */
143 for (j=1; size>=j; j++)
144 {
145 /* for each column */
146 if (UNFILLED == tbl[i][j])
147 {
148 /* found one of the implied partition */
149 start[0][R] = i;
150 start[0][C] = j;
151 i = size + 1;
152 j = size + 1;
153 } /* found one of the implied partition */
154 } /* for each column */
155 } /* for each row */
156 } /* FUNCTION findZero */
157
158 int fill(int row, int col, int part)
159 {
160 /* FUNCTION fill */
161 int ret = 0;
162
163 if (part == tbl[row][col])
164 {
165 /* still in partition */
166 ret = 1;
167 tbl[row][col] = FILLED;
168 ret = ret + fill(row - 1, col, part);
169 ret = ret + fill(row + 1, col, part);
170 ret = ret + fill(row, col - 1, part);
171 ret = ret + fill(row, col + 1, part);
172 } /* still in partition */
173 return ret;
174 } /* FUNCTION fill */
175
176 int anyLeft()
177 {
178 /* FUNCTION anyLeft */
179 int i;
180 int j;
181 int found = FALSE;
182
183 for (i=1; size>=i; i++)
184 {
185 /* for each row */
186 for (j=1; size>=j; j++)
187 {
188 /* for each column */
189 if (FILLED != tbl[i][j])
190 {
191 /* found one */
192 found = TRUE;
193 i = size + 1;
194 j = size + 1;
195 } /* found one */
196 } /* for each column */
197 } /* for each row */
198 return found;
199 } /* FUNCTION anyLeft */
200
201 void process()
202 {
203 /* FUNCTION process */
204 int i;
205 int valid = TRUE;
206 int tmp;
207
208 if (1 == size)
209 {
210 /* trivial case */
211 printf("good\n");
212 } /* trivial case */
213 else
214 {
215 /* normal cases */
216 DEBUG dump();
217 findZero();
218 DEBUG dump();
219 /*
220 for (i=0; (size>i); i++)
221 */
222 for (i=0; (valid) && (size>i); i++)
223 {
224 /* fill each partition starting at first known member */
225 tmp = fill(start[i][R], start[i][C], i);
226 DEBUG printf("%d: %d\n", i, tmp);
227 valid = valid && (size == tmp);
228 } /* fill each partition starting at first known member */
229 /* if any remaining unfilled spots, then this is wrong */
230 if ((!valid) || (anyLeft()))
231 {
232 /* wrong */
233 printf("wrong\n");
234 } /* wrong */
235 else
236 {
237 /* good */
238 printf("good\n");
239 } /* good */
240 } /* normal cases */
241 } /* FUNCTION process */
242
243 int main()
244 {
245 /* main */
246 int moreToDo;
247
248 init();
249 moreToDo = getInput();
250 while (moreToDo)
251 {
252 /* while */
253 process();
254 moreToDo = getInput();
255 } /* while */
256
257 return EXIT_SUCCESS;
258 } /* main */
259