/home/toolbox/public_html/solutions/5/532/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 (TRUE)
14
15 /*
16 * Author: Isaac Traxler
17 * Date: 2018-03-11
18 * Purpose: fun
19 * Problem: 532 - Dungeon Master
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24 */
25
26
27 #define MAX_DIM 33
28 #define MXX (MAX_DIM * MAX_DIM * MAX_DIM)
29 #define illegal -99
30 #define block -1
31 #define vacant 0
32
33 typedef struct LOCATION_STRUCT
34 {
35 int p; /* plane or page */
36 int r; /* row */
37 int c; /* column */
38 }
39 LOCATION_STRUCT;
40
41
42 int dungeon[MAX_DIM][MAX_DIM][MAX_DIM];
43
44 LOCATION_STRUCT stk[MXX][2];
45 int stackTop[2];
46 LOCATION_STRUCT count;
47 LOCATION_STRUCT start;
48 LOCATION_STRUCT goal;
49 LOCATION_STRUCT delta[6] = { { 0, 0,-1 },
50 { 0, 0, 1 },
51 { 0, 1, 0 },
52 { 0,-1, 0 },
53 { 1, 0, 0 },
54 { -1, 0, 0 }
55 };
56 int otherStack[2] = { 1, 0};
57
58 void init()
59 {
60 /* FUNCTION init */
61 int p;
62 int r;
63 int c;
64
65 for (p=0; MAX_DIM>p; p++)
66 for (r=0; MAX_DIM>r; r++)
67 for (c=0; MAX_DIM>c; c++)
68 dungeon[p][r][c] = illegal;
69 stackTop[0] = 0;
70 stackTop[1] = 0;
71 } /* FUNCTION init */
72
73 void dump()
74 {
75 /* FUNCTION dump */
76 int p;
77 int r;
78 int c;
79
80 printf("%d %d %d\n", start.p, start.r, start.c);
81 for (p=0; (count.p+2)>p; p++)
82 {
83 /* for p */
84 for (r=0; (count.r+2)>r; r++)
85 {
86 /* for r */
87 for (c=0; (count.c+2)>c; c++)
88 {
89 /* for c */
90 printf("%4d", dungeon[p][r][c]);
91 } /* for c */
92 printf("\n");
93 } /* for r */
94 printf("\n");
95 } /* for p */
96 } /* FUNCTION dump */
97
98 int getInput()
99 {
100 /* FUNCTION getInput */
101 int dataReadFlag;
102 int p;
103 int r;
104 int c;
105 int l;
106 char line[MAX_DIM];
107
108 init();
109 scanf(" %d %d %d ", &count.p, &count.r, &count.c);
110 dataReadFlag = ((0 != count.p) || (0 != count.r) || (0 != count.c));
111 if (dataReadFlag)
112 {
113 /* read the dungeon */
114 for (p=1; count.p>=p; p++)
115 {
116 /* for each plane */
117 for (r=1; count.r>=r; r++)
118 {
119 /* for each row */
120 scanf(" %s ", line);
121 for (c=1,l=0; count.c>=c; c++,l++)
122 {
123 /* process a cell */
124 switch (line[l])
125 {
126 /* switch */
127 case '#':
128 dungeon[p][r][c] = block;
129 break;
130 case '.':
131 dungeon[p][r][c] = vacant;
132 break;
133 case 'S':
134 dungeon[p][r][c] = vacant;
135 start.p = p;
136 start.r = r;
137 start.c = c;
138 break;
139 case 'E':
140 dungeon[p][r][c] = vacant;
141 goal.p = p;
142 goal.r = r;
143 goal.c = c;
144 break;
145 } /* switch */
146 } /* process a cell */
147 } /* for each row */
148 } /* for each plane */
149 } /* read the dungeon */
150 return (dataReadFlag);
151 } /* FUNCTION getInput */
152
153 void push(LOCATION_STRUCT t, int stack)
154 {
155 /* FUNCTION push */
156 stk[stackTop[stack]][stack].p = t.p;
157 stk[stackTop[stack]][stack].r = t.r;
158 stk[stackTop[stack]][stack].c = t.c;
159 DEBUG printf("push: %d (%d,%d,%d) = %d\n",stackTop[stack], stk[stackTop[stack]][stack].p, stk[stackTop[stack]][stack].r, stk[stackTop[stack]][stack].c, dungeon[t.p][t.r][t.c]);
160 stackTop[stack]++;
161 } /* FUNCTION push */
162
163 int movesToMake(int stack)
164 {
165 /* FUNCTION movesToMake */
166 return (0 < stackTop[stack]);
167 } /* FUNCTION movesToMake */
168
169 LOCATION_STRUCT pop(int stack)
170 {
171 /* FUNCTION pop */
172 stackTop[stack]--;
173 DEBUG printf("pop: %d (%d,%d,%d) = %d \n",stackTop[stack], stk[stackTop[stack]][stack].p, stk[stackTop[stack]][stack].r, stk[stackTop[stack]][stack].c, dungeon[stk[stackTop[stack]][stack].p][stk[stackTop[stack]][stack].r][stk[stackTop[stack]][stack].c]);
174
175 return (stk[stackTop[stack]][stack]);
176 } /* FUNCTION pop */
177
178 int move(int stack)
179 {
180 /* FUNCTON move */
181 LOCATION_STRUCT loc;
182
183 loc = pop(stack);
184 return (dungeon[loc.p][loc.r][loc.c]);
185 } /* FUNCTON move */
186
187 void checkForMoves(LOCATION_STRUCT loc, int steps, int stack)
188 {
189 /* FUNCTON checkForMoves */
190 int i;
191 int p;
192 int r;
193 int c;
194 LOCATION_STRUCT tmp;
195
196 /* need to check all 6 possible moves using delta */
197 for (i=0; 6>i; i++)
198 {
199 /* for */
200 p = loc.p + delta[i].p;
201 r = loc.r + delta[i].r;
202 c = loc.c + delta[i].c;
203 tmp.p = p;
204 tmp.r = r;
205 tmp.c = c;
206 if ((block != dungeon[p][r][c]) && (illegal != dungeon[p][r][c]))
207 {
208 /* we can potentially move here */
209 if (vacant == dungeon[p][r][c])
210 {
211 /* spot has never been visited */
212 dungeon[p][r][c] = steps;
213 push(tmp, stack);
214 } /* spot has never been visited */
215 if (steps < dungeon[p][r][c]) /* this should never happen */
216 {
217 /* shorter path */
218 dungeon[p][r][c] = steps;
219 push(tmp, stack);
220 } /* shorter path */
221 } /* we can potentially move here */
222 } /* for */
223 } /* FUNCTON checkForMoves */
224
225 void makeAllMoves(int stack)
226 {
227 /* FUNCTION makeAllMoves */
228 int stp;
229 LOCATION_STRUCT loc;
230
231 while (movesToMake(stack))
232 {
233 /* while there are moves to make */
234 loc = pop(stack);
235 stp = dungeon[loc.p][loc.r][loc.c] + 1;
236 checkForMoves(loc, stp, otherStack[stack]);
237 } /* while there are moves to make */
238 } /* FUNCTION makeAllMoves */
239
240 void process()
241 {
242 /* FUNCTION process */
243 LOCATION_STRUCT loc;
244 int steps = 1;
245 int stack = 0;
246
247 loc = start;
248 DEBUG printf("Start at (%d,%d,%d)\n", loc.p, loc.r, loc.c);
249 dungeon[loc.p][loc.r][loc.c] = steps;
250 push(loc, stack);
251 while (movesToMake(stack))
252 {
253 /* while moves still possible */
254 makeAllMoves(stack);
255 stack = otherStack[stack]; /* flip to other stack */
256 } /* while moves still possible */
257 DEBUG dump();
258 DEBUG printf("solution counf is %d\n", dungeon[goal.p][goal.r][goal.c]);
259 /* since start is considered 1 instead of 0, everything is inflated by one */
260 dungeon[goal.p][goal.r][goal.c]--;
261 if (1 > dungeon[goal.p][goal.r][goal.c])
262 {
263 /* no solutions */
264 printf("Trapped!\n");
265 } /* no solutions */
266 else
267 {
268 /* solution found */
269 printf("Escaped in %d minute(s).\n", dungeon[goal.p][goal.r][goal.c]);
270 } /* solution found */
271 } /* FUNCTION process */
272
273 int main()
274 {
275 /* main */
276 int moreToDo;
277
278 moreToDo = getInput();
279 while (moreToDo)
280 {
281 /* while */
282 process();
283 moreToDo = getInput();
284 } /* while */
285
286 return EXIT_SUCCESS;
287 } /* main */
288