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