/home/toolbox/public_html/solutions/109/10977/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 DEBUG1 if (FALSE)
14 #define DEBUG2 if (FALSE)
15 #define DEBUG3 if (TRUE)
16
17 /*
18 * Author:
19 * Date:
20 * Purpose:
21 * Problem: 10977
22 */
23
24 /*
25 * This template reads data until a terminating value is reached.
26 */
27
28 #define MAXSIZE 205
29 #define MASKSIZE 102
30 #define BLOCKED1 -1
31 #define BLOCKED2 -2
32 #define BLOCKED3 -3
33
34 int R;
35 int C;
36 int M;
37
38 int ef[MAXSIZE][MAXSIZE];
39 int mask[MASKSIZE][MASKSIZE];
40
41 void dump()
42 {
43 /* FUNCTION dump */
44 int i;
45 int j;
46
47 for (i=0; i<(R+2); i++)
48 {
49 for (j=0; j<(C+2); j++)
50 {
51 printf("%5d ", ef[i][j]);
52 }
53 printf("\n");
54 }
55 printf("\n");
56 } /* FUNCTION dump */
57
58 void dumpMask()
59 {
60 /* FUNCTION dumpMask */
61 int i;
62 int j;
63
64 for (i=0; i<10; i++)
65 {
66 for (j=0; j<10; j++)
67 {
68 printf("%3d ", mask[i][j]);
69 }
70 printf("\n");
71 }
72 printf("\n");
73 } /* FUNCTION dumpMask */
74
75 void init()
76 {
77 /* FUNCTION init */
78 int i;
79 int j;
80 int t1;
81 int t2;
82 int start;
83
84 memset(mask, 0, sizeof(mask));
85 for (i=0; i<MASKSIZE; i++)
86 {
87 t1 = i * i;
88 for (j=0; j<MASKSIZE; j++)
89 {
90 t2 = t1 + j * j;
91 mask[i][j] = t2;
92 DEBUG2 printf("[%d][%d] = %d\n", i, j, mask[i][j]);
93 }
94 }
95 DEBUG2 dumpMask();
96 } /* FUNCTION init */
97
98 void doPuff(int a, int b, int c)
99 {
100 /* BEGIN FUNCTION doBuff */
101 int i;
102 int j;
103 int c2;
104
105 c2 = c * c;
106 DEBUG2 dump();
107 for (i=0; i<=c; i++)
108 {
109 /*
110 for (j=0; (j<c) && (ef[i][j]<c2); j++)
111 */
112 for (j=0; j<=c; j++)
113 {
114 if (c2 >= mask[i][j])
115 {
116 DEBUG2 printf("%d block %d-%d:%d\n", c2, i, j, mask[i][j]);
117 ef[a+i][b+j] = BLOCKED3;
118 ef[a-i][b+j] = BLOCKED3;
119 ef[a+i][b-j] = BLOCKED3;
120 ef[a-i][b-j] = BLOCKED3;
121 }
122 }
123 }
124 DEBUG2 dump();
125 } /* END FUNCTION doBuff */
126
127
128
129 int getInput()
130 {
131 /* FUNCTION getInput */
132 int dataReadFlag;
133 int i;
134 int j;
135 int a;
136 int b;
137 int c;
138 int puffs;
139
140 scanf("%d %d\n", &R, &C);
141 if ((0 != R) && (0 != C))
142 {
143 /* something to do */
144 dataReadFlag = TRUE;
145 memset(ef,0,sizeof(ef));
146 /* mark bounds */
147 for (i=0; i<(C+2); i++)
148 {
149 /* outer loop */
150 ef[0][i] = BLOCKED1;
151 ef[R+1][i] = BLOCKED1;
152 } /* outer loop */
153 for (i=0; i<(R+2); i++)
154 {
155 /* outer loop */
156 ef[i][0] = BLOCKED1;
157 ef[i][C+1] = BLOCKED1;
158 } /* outer loop */
159 /* do blocks */
160 scanf("%d\n", &M);
161 for (i=0; i<M; i++)
162 {
163 /* each block */
164 scanf("%d %d\n", &a, &b);
165 ef[a][b] = BLOCKED2;
166 } /* each block */
167 /* do the puffs */
168 scanf("%d\n", &puffs);
169 for (i=0; i<puffs; i++)
170 {
171 /* each puff */
172 scanf("%d %d %d\n", &a, &b, &c);
173 doPuff(a, b, c);
174 } /* each puff */
175 } /* something to do */
176 else
177 {
178 /* nothing read */
179 dataReadFlag = FALSE;
180 } /* nothing read */
181 return (dataReadFlag);
182 } /* FUNCTION getInput */
183
184 int doit(int i, int j)
185 {
186 /* BEGIN FUNCTION doit */
187 int tmp;
188 int retVal = 0;
189
190 if (0 == ef[i+1][j])
191 {
192 ef[i+1][j] = ef[i][j] + 1;
193 retVal = 1;
194 }
195 if (0 == ef[i-1][j])
196 {
197 ef[i-1][j] = ef[i][j] + 1;
198 retVal = 1;
199 }
200 if (0 == ef[i][j+1])
201 {
202 ef[i][j+1] = ef[i][j] + 1;
203 retVal = 1;
204 }
205 if (0 == ef[i][j-1])
206 {
207 ef[i][j-1] = ef[i][j] + 1;
208 retVal = 1;
209 }
210
211 tmp = ef[i][j] + 1;
212 if (tmp < ef[i+1][j])
213 {
214 ef[i+1][j] = tmp;
215 retVal = 1;
216 }
217 if (tmp < ef[i-1][j])
218 {
219 ef[i-1][j] = tmp;
220 retVal = 1;
221 }
222 if (tmp < ef[i][j+1])
223 {
224 ef[i][j+1] = tmp;
225 retVal = 1;
226 }
227 if (tmp < ef[i][j-1])
228 {
229 ef[i][j-1] = tmp;
230 retVal = 1;
231 }
232
233 } /* END FUNCTION doit */
234
235 void floodFill()
236 {
237 /* BEGIN FUNCTION floodFill */
238 int i;
239 int j;
240 int impossible = FALSE;
241 int cr;
242 int cc;
243 int chg;
244
245 if ((0 !=ef[1][1]) || (0 !=ef[R][C]))
246 {
247 /* entrance or exit blocked */
248 ef[R][C] = BLOCKED1;
249 } /* entrance or exit blocked */
250 else
251 {
252 /* start is clear */
253 chg = 1;
254 while (0 != chg)
255 {
256 chg = 0;
257 cr = 1;
258 cc = 1;
259 ef[cr][cc] = 1;
260 for (i=0; i<=R; i++)
261 {
262 /* row */
263 for (j=0; j<=R; j++)
264 {
265 /* col */
266 if (0 < ef[i][j])
267 {
268 /* at a valid place */
269 chg = chg + doit(i,j);
270 printf("\ni=%d(%d) j=%d(%d)\n",i,R,j,C);
271 dump();
272 } /* at a valid place */
273 } /* col */
274 } /* row */
275 } /* start is clear */
276 }
277 } /* END FUNCTION floodFill */
278
279 void process()
280 {
281 /* FUNCTION process */
282 floodFill();
283 if (1 > ef[R][C])
284 printf("Impossible.\n");
285 else
286 printf("%d\n", ef[R][C]-1);
287 } /* FUNCTION process */
288
289 int main ()
290 {
291 /* main */
292 int moreToDo;
293
294 init();
295 moreToDo = getInput();
296 while (moreToDo)
297 {
298 /* while */
299 process();
300 DEBUG2 dump();
301 moreToDo = getInput();
302 } /* while */
303
304 return EXIT_SUCCESS;
305 } /* main */
306