|
1 #include <stdio.h> |
|
2 #include <string.h> |
|
3 |
|
4 #define BOX '*' |
|
5 #define WALL '#' |
|
6 #define MAN '8' |
|
7 #define PLATFORM '+' |
|
8 #define BOXINPLATFORM 'O' |
|
9 #define MANINPLATFORM 'E' |
|
10 #define BLANK ' ' |
|
11 |
|
12 #define DIR_LEFT 'A' |
|
13 #define DIR_RIGHT 'B' |
|
14 #define DIR_UP 'C' |
|
15 #define DIR_DOWN 'D' |
|
16 |
|
17 #define MAX_X 500 |
|
18 #define MAX_Y 500 |
|
19 #define MAX_MOVES 100 |
|
20 |
|
21 /* SOKOBAN Solution Finder |
|
22 * |
|
23 * Cerca totes les possibilitats de tots els nombres de combinacions possibles, |
|
24 * menys la que tots els moviments són a l'esquerra del número de combinacions |
|
25 * incials triat. |
|
26 */ |
|
27 |
|
28 |
|
29 struct Map |
|
30 { |
|
31 char Cells[MAX_X][MAX_Y]; |
|
32 int SizeX, SizeY; |
|
33 int ManX, ManY; |
|
34 int NumPlatforms; |
|
35 int NumBoxesInPlatform; |
|
36 }; |
|
37 |
|
38 |
|
39 |
|
40 void ReadMap(struct Map *M, char *FileName) |
|
41 { |
|
42 FILE *Fitxer; |
|
43 int i,j; |
|
44 |
|
45 if(!(Fitxer = fopen(FileName, "r"))) |
|
46 { |
|
47 printf("Error opening %s!", FileName); |
|
48 exit(1); |
|
49 } |
|
50 |
|
51 M->SizeX=0; |
|
52 M->SizeY=0; |
|
53 while (!feof(Fitxer)) |
|
54 { |
|
55 fgets(M->Cells[M->SizeY++], MAX_X, Fitxer); |
|
56 } |
|
57 M->SizeY--; |
|
58 M->SizeX = strlen(M->Cells[0]) - 1; |
|
59 |
|
60 M->NumPlatforms = 0; |
|
61 M->NumBoxesInPlatform = 0; |
|
62 for (j = 0; j<M->SizeY; j++) |
|
63 for (i=0; i<M->SizeX; i++) |
|
64 { |
|
65 if (M->Cells[j][i] == MAN) |
|
66 { M->ManX = i; M->ManY = j; } |
|
67 else if (M->Cells[j][i] == PLATFORM) |
|
68 M->NumPlatforms++; |
|
69 else if (M->Cells[j][i] == BOXINPLATFORM) |
|
70 { |
|
71 M->NumPlatforms++; |
|
72 M->NumBoxesInPlatform++; |
|
73 } |
|
74 } |
|
75 } |
|
76 |
|
77 |
|
78 void ShowMap (struct Map *M) |
|
79 { |
|
80 int i,j; |
|
81 for (j = 0; j<M->SizeY; j++) |
|
82 { |
|
83 for (i=0; i<M->SizeX; i++) |
|
84 printf("%c", M->Cells[j][i]); |
|
85 printf("\n"); |
|
86 } |
|
87 printf("Man is at (%i,%i)\n", M->ManX, M->ManY); |
|
88 printf("Platforms: %i, BoxesInPlatform: %i\n", M->NumPlatforms, |
|
89 M->NumBoxesInPlatform); |
|
90 } |
|
91 |
|
92 |
|
93 |
|
94 void CopyMap (struct Map *Mdest, struct Map *Morig) |
|
95 { |
|
96 memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map)); |
|
97 } |
|
98 |
|
99 int MoveMan (struct Map *M, int Direction) |
|
100 { |
|
101 int NewX, NewY; |
|
102 |
|
103 /* |
|
104 // Check if man is where it should be |
|
105 if (M->Cells[M->ManY][M->ManX] != MAN && |
|
106 M->Cells[M->ManY][M->ManX] != MANINPLATFORM) |
|
107 { |
|
108 printf("Man isn't where it should be!\n"); |
|
109 exit(2); |
|
110 } |
|
111 */ |
|
112 |
|
113 // Process Movement |
|
114 if (Direction == DIR_LEFT) |
|
115 { NewX = M->ManX - 1; NewY = M->ManY; } |
|
116 else if (Direction == DIR_RIGHT) |
|
117 { NewX = M->ManX + 1; NewY = M->ManY; } |
|
118 else if (Direction == DIR_UP) |
|
119 { NewX = M->ManX; NewY = M->ManY - 1; } |
|
120 else if (Direction == DIR_DOWN) // if not needed |
|
121 { NewX = M->ManX; NewY = M->ManY + 1; } |
|
122 |
|
123 |
|
124 |
|
125 // What's in front of the man? |
|
126 |
|
127 if (M->Cells[NewY][NewX] == WALL) |
|
128 { |
|
129 return 0; // ILLEGAL MOVE |
|
130 } |
|
131 else if (M->Cells[NewY][NewX] == BOX) |
|
132 { |
|
133 if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == |
|
134 BLANK) |
|
135 { |
|
136 M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] |
|
137 = BOX; |
|
138 |
|
139 if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) |
|
140 { // Man is over Platform |
|
141 M->Cells[M->ManY][M->ManX] = PLATFORM; |
|
142 M->Cells[NewY][NewX] = MAN; |
|
143 } |
|
144 else // Man is over Blank |
|
145 { |
|
146 M->Cells[M->ManY][M->ManX] = BLANK; |
|
147 M->Cells[NewY][NewX] = MAN; |
|
148 } |
|
149 M->ManX = NewX; M->ManY = NewY; |
|
150 return 1; |
|
151 } |
|
152 else |
|
153 if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == |
|
154 PLATFORM) |
|
155 { |
|
156 M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] |
|
157 = BOXINPLATFORM; |
|
158 |
|
159 if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) |
|
160 { // Man is over Platform |
|
161 M->Cells[M->ManY][M->ManX] = PLATFORM; |
|
162 M->Cells[NewY][NewX] = MAN; |
|
163 } |
|
164 else // Man is over Blank |
|
165 { |
|
166 M->Cells[M->ManY][M->ManX] = BLANK; |
|
167 M->Cells[NewY][NewX] = MAN; |
|
168 } |
|
169 M->ManX = NewX; M->ManY = NewY; |
|
170 |
|
171 M->NumBoxesInPlatform++; |
|
172 return 1; |
|
173 } |
|
174 else |
|
175 { |
|
176 return 0; // ILLEGAL MOVE |
|
177 } |
|
178 }else |
|
179 if (M->Cells[NewY][NewX] == BOXINPLATFORM) |
|
180 { |
|
181 if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == |
|
182 BLANK) |
|
183 { |
|
184 M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] |
|
185 = BOX; |
|
186 |
|
187 if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) |
|
188 { // Man is over Platform |
|
189 M->Cells[M->ManY][M->ManX] = PLATFORM; |
|
190 M->Cells[NewY][NewX] = MANINPLATFORM; |
|
191 } |
|
192 else // Man is over Blank |
|
193 { |
|
194 M->Cells[M->ManY][M->ManX] = BLANK; |
|
195 M->Cells[NewY][NewX] = MANINPLATFORM; |
|
196 } |
|
197 M->ManX = NewX; M->ManY = NewY; |
|
198 M->NumBoxesInPlatform--; |
|
199 return 1; |
|
200 } |
|
201 else |
|
202 if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] == |
|
203 PLATFORM) |
|
204 { |
|
205 M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] |
|
206 = BOXINPLATFORM; |
|
207 |
|
208 if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) |
|
209 { // Man is over Platform |
|
210 M->Cells[M->ManY][M->ManX] = PLATFORM; |
|
211 M->Cells[NewY][NewX] = MANINPLATFORM; |
|
212 } |
|
213 else // Man is over Blank |
|
214 { |
|
215 M->Cells[M->ManY][M->ManX] = BLANK; |
|
216 M->Cells[NewY][NewX] = MANINPLATFORM; |
|
217 } |
|
218 M->ManX = NewX; M->ManY = NewY; |
|
219 return 1; |
|
220 } |
|
221 else |
|
222 { |
|
223 return 0; // ILLEGAL MOVE |
|
224 } |
|
225 } |
|
226 else if (M->Cells[NewY][NewX] == PLATFORM) |
|
227 { |
|
228 if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) |
|
229 { // Man is over Platform |
|
230 M->Cells[M->ManY][M->ManX] = PLATFORM; |
|
231 M->Cells[NewY][NewX] = MANINPLATFORM; |
|
232 } |
|
233 else // Man is over Blank |
|
234 { |
|
235 M->Cells[M->ManY][M->ManX] = BLANK; |
|
236 M->Cells[NewY][NewX] = MANINPLATFORM; |
|
237 } |
|
238 M->ManX = NewX; M->ManY = NewY; |
|
239 return 1; |
|
240 } |
|
241 else if (M->Cells[NewY][NewX] == BLANK) // IF not needed |
|
242 { |
|
243 if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM) |
|
244 { // Man is over Platform |
|
245 M->Cells[M->ManY][M->ManX] = PLATFORM; |
|
246 M->Cells[NewY][NewX] = MAN; |
|
247 } |
|
248 else // Man is over Blank |
|
249 { |
|
250 M->Cells[M->ManY][M->ManX] = BLANK; |
|
251 M->Cells[NewY][NewX] = MAN; |
|
252 } |
|
253 M->ManX = NewX; M->ManY = NewY; |
|
254 return 1; |
|
255 } |
|
256 return 1; |
|
257 } |
|
258 |
|
259 int main(int argn, char **argv) |
|
260 { |
|
261 struct Map Morigin, M[MAX_MOVES]; |
|
262 char Moves[MAX_MOVES]; |
|
263 int NumMoves; |
|
264 int OldMaps; |
|
265 int IllegalMove; |
|
266 int Carry; |
|
267 |
|
268 int i, j; |
|
269 |
|
270 if (argn != 2) |
|
271 { |
|
272 printf("Usage: %s <mapfile> <initial NumMoves>\n", argv[0]); |
|
273 exit(3); |
|
274 } |
|
275 |
|
276 ReadMap(&Morigin, argv[1]); |
|
277 sscanf(argv[2], "%i", &NumMoves); |
|
278 |
|
279 ShowMap(&Morigin); |
|
280 |
|
281 CopyMap(&M, &Morigin); |
|
282 |
|
283 IllegalMove = NumMoves - 1; |
|
284 |
|
285 for (i = 0; i < NumMoves; i++) |
|
286 Moves[i] = DIR_LEFT; |
|
287 |
|
288 // Reget the original map |
|
289 CopyMap(&M[0], &Morigin); |
|
290 |
|
291 OldMaps = 0; |
|
292 |
|
293 IllegalMove = NumMoves - 1; |
|
294 // Process the combination |
|
295 for (i = 0; i < NumMoves; i++) |
|
296 { |
|
297 CopyMap(&M[i+1], &M[i]); |
|
298 // Could we use OldMaps for indexing, as faster than i+1? |
|
299 if (!MoveMan(&M[i+1], Moves[i])) |
|
300 { |
|
301 IllegalMove = i; |
|
302 break; |
|
303 } |
|
304 } |
|
305 |
|
306 // Process the combinations. |
|
307 // Order: Left, Right, Up, Down |
|
308 while (M.NumPlatforms != M.NumBoxesInPlatform) |
|
309 { |
|
310 // Increase the Counter |
|
311 { |
|
312 Carry = 1; |
|
313 // Reset the direction of sure-invalid moves |
|
314 for (i = IllegalMove + 1; i < NumMoves; i++) |
|
315 Moves[i] = DIR_LEFT; |
|
316 // Increase Counter for a new try of moves |
|
317 for (i = IllegalMove; i >= 0 && Carry; i--) |
|
318 { |
|
319 Moves[i]++; |
|
320 if (Moves[i] == DIR_DOWN + 1) |
|
321 { Moves[i] = DIR_LEFT; Carry = 1; } |
|
322 } |
|
323 OldMaps = i; // Sure? |
|
324 // If we change the number of movements for solution |
|
325 if (Carry) |
|
326 { |
|
327 if (NumMoves > MAX_MOVES) |
|
328 break; // MAX MOVES EXCEEDED!!! |
|
329 NumMoves++; |
|
330 for (i = 0; i < NumMoves; i++) |
|
331 Moves[i] = DIR_LEFT; |
|
332 printf("Provant %i moviments...\n", NumMoves); |
|
333 } |
|
334 } |
|
335 |
|
336 /* |
|
337 // Print the combination |
|
338 |
|
339 for (i=0; i < NumMoves; i++) |
|
340 { |
|
341 printf("%c", Moves[i]); |
|
342 } |
|
343 printf("\n"); |
|
344 */ |
|
345 |
|
346 IllegalMove = NumMoves - 1; |
|
347 // Process the combination |
|
348 for (i = 0; i < NumMoves; i++) |
|
349 { |
|
350 if (i>=OldMaps) |
|
351 { |
|
352 CopyMap(&M[i+1], &M[i]); |
|
353 if (!MoveMan(&M[i+1], Moves[i])) |
|
354 { |
|
355 IllegalMove = i; |
|
356 break; |
|
357 } |
|
358 } |
|
359 } |
|
360 |
|
361 } |
|
362 |
|
363 // Print the combination |
|
364 for (i=0; i < NumMoves; i++) |
|
365 { |
|
366 printf("%c", Moves[i]); |
|
367 } |
|
368 printf("\n"); |
|
369 |
|
370 /* |
|
371 // Print The Steps |
|
372 strcpy(Moves, "DDDRUU"); |
|
373 |
|
374 for (i=0; i < 6; i++) |
|
375 { |
|
376 printf("%i", MoveMan(&M, Moves[i])); |
|
377 ShowMap(&M); |
|
378 } |
|
379 */ |
|
380 |
|
381 } |