/home/toolbox/public_html/solutions/5/532/w.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: 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];
45 int stackTop;
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
57 void init()
58 {
59 /* FUNCTION init */
60 int p;
61 int r;
62 int c;
63
64 for (p=0; MAX_DIM>p; p++)
65 for (r=0; MAX_DIM>r; r++)
66 for (c=0; MAX_DIM>c; c++)
67 dungeon[p][r][c] = illegal;
68 stackTop = 0;
69 } /* FUNCTION init */
70
71 void dump()
72 {
73 /* FUNCTION dump */
74 int p;
75 int r;
76 int c;
77
78 printf("%d %d %d\n", start.p, start.r, start.c);
79 for (p=0; (count.p+2)>p; p++)
80 {
81 /* for p */
82 for (r=0; (count.r+2)>r; r++)
83 {
84 /* for r */
85 for (c=0; (count.c+2)>c; c++)
86 {
87 /* for c */
88 printf("%4d", dungeon[p][r][c]);
89 } /* for c */
90 printf("\n");
91 } /* for r */
92 printf("\n");
93 } /* for p */
94 } /* FUNCTION dump */
95
96 int getInput()
97 {
98 /* FUNCTION getInput */
99 int dataReadFlag;
100 int p;
101 int r;
102 int c;
103 int l;
104 char line[MAX_DIM];
105
106 init();
107 scanf(" %d %d %d ", &count.p, &count.r, &count.c);
108 dataReadFlag = ((0 != count.p) || (0 != count.r) || (0 != count.c));
109 if (dataReadFlag)
110 {
111 /* read the dungeon */
112 for (p=1; count.p>=p; p++)
113 {
114 /* for each plane */
115 for (r=1; count.r>=r; r++)
116 {
117 /* for each row */
118 scanf(" %s ", line);
119 for (c=1,l=0; count.c>=c; c++,l++)
120 {
121 /* process a cell */
122 switch (line[l])
123 {
124 /* switch */
125 case '#':
126 dungeon[p][r][c] = block;
127 break;
128 case '.':
129 dungeon[p][r][c] = vacant;
130 break;
131 case 'S':
132 dungeon[p][r][c] = vacant;
133 start.p = p;
134 start.r = r;
135 start.c = c;
136 break;
137 case 'E':
138 dungeon[p][r][c] = vacant;
139 goal.p = p;
140 goal.r = r;
141 goal.c = c;
142 break;
143 } /* switch */
144 } /* process a cell */
145 } /* for each row */
146 } /* for each plane */
147 } /* read the dungeon */
148 return (dataReadFlag);
149 } /* FUNCTION getInput */
150
151 void push(LOCATION_STRUCT t)
152 {
153 /* FUNCTION push */
154 stk[stackTop].p = t.p;
155 stk[stackTop].r = t.r;
156 stk[stackTop].c = t.c;
157 DEBUG printf("push: %d (%d,%d,%d) = %d\n",stackTop, stk[stackTop].p, stk[stackTop].r, stk[stackTop].c, dungeon[t.p][t.r][t.c]);
158 stackTop++;
159 } /* FUNCTION push */
160
161 int movesToMake()
162 {
163 /* FUNCTION movesToMake */
164 return (0 < stackTop);
165 } /* FUNCTION movesToMake */
166
167 LOCATION_STRUCT pop()
168 {
169 /* FUNCTION pop */
170 stackTop--;
171 DEBUG printf("pop: %d (%d,%d,%d) = %d \n",stackTop, stk[stackTop].p, stk[stackTop].r, stk[stackTop].c, dungeon[stk[stackTop].p][stk[stackTop].r][stk[stackTop].c]);
172
173 return (stk[stackTop]);
174 } /* FUNCTION pop */
175
176 int move()
177 {
178 /* FUNCTON move */
179 LOCATION_STRUCT loc;
180
181 loc = pop();
182 return (dungeon[loc.p][loc.r][loc.c]);
183 } /* FUNCTON move */
184
185 void checkForMoves(int steps)
186 {
187 /* FUNCTON checkForMoves */
188 int i;
189 int p;
190 int r;
191 int c;
192 LOCATION_STRUCT loc;
193 LOCATION_STRUCT tmp;
194
195 /* need to check all 6 possible moves using delta */
196 for (i=0; 6>i; i++)
197 {
198 /* for */
199 p = loc.p + delta[i].p;
200 r = loc.r + delta[i].r;
201 c = loc.c + delta[i].c;
202 tmp.p = p;
203 tmp.r = r;
204 tmp.c = c;
205 if ((block != dungeon[p][r][c]) && (illegal != dungeon[p][r][c]))
206 {
207 /* we can potentially move here */
208 if (vacant == dungeon[p][r][c])
209 {
210 /* spot has never been visited */
211 dungeon[p][r][c] = steps;
212 push(tmp);
213 } /* spot has never been visited */
214 if (steps < dungeon[p][r][c])
215 {
216 /* shorter path */
217 dungeon[p][r][c] = steps;
218 push(tmp);
219 } /* shorter path */
220 } /* we can potentially move here */
221 } /* for */
222 } /* FUNCTON checkForMoves */
223
224 void process()
225 {
226 /* FUNCTION process */
227 LOCATION_STRUCT loc;
228 int steps = 1;
229
230 loc = start;
231 DEBUG printf("Start at (%d,%d,%d)\n", loc.p, loc.r, loc.c);
232 dungeon[loc.p][loc.r][loc.c] = steps;
233 push(loc);
234 while (movesToMake())
235 {
236 /* while moves still possible */
237 steps = move() + 1;
238 checkForMoves(steps);
239 } /* while moves still possible */
240 DEBUG dump();
241 DEBUG printf("solution counf is %d\n", dungeon[goal.p][goal.r][goal.c]);
242 /* since start is considered 1 instead of 0, everything is inflated by one */
243 dungeon[goal.p][goal.r][goal.c]--;
244 if (1 > dungeon[goal.p][goal.r][goal.c])
245 {
246 /* no solutions */
247 printf("Trapped!\n");
248 } /* no solutions */
249 else
250 {
251 /* solution found */
252 printf("Escaped in %d minute(s).\n", dungeon[goal.p][goal.r][goal.c]);
253 } /* solution found */
254 } /* FUNCTION process */
255
256 int main()
257 {
258 /* main */
259 int moreToDo;
260
261 moreToDo = getInput();
262 while (moreToDo)
263 {
264 /* while */
265 process();
266 moreToDo = getInput();
267 } /* while */
268
269 return EXIT_SUCCESS;
270 } /* main */
271