--- a/sokosol4.c Fri May 05 23:18:24 2006 +0200
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,366 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-
-#define BOX '$'
-#define WALL '#'
-#define MAN '@'
-#define PLATFORM '.'
-#define BOXINPLATFORM '*'
-#define MANINPLATFORM 'E'
-#define BLANK ' '
-#define CANTO '-'
-
-#define DIR_LEFT 'A'
-#define DIR_RIGHT 'B'
-#define DIR_UP 'C'
-#define DIR_DOWN 'D'
-
-#define MAX_X 50
-#define MAX_Y 50
-#define MAX_MOVES 50
-
-#define MOVE_OK 1
-#define MOVE_BOX 2
-#define MOVE_ILLEGAL 0
-
-/* SOKOBAN Solution Finder
- *
- * Cerca totes les possibilitats de tots els nombres de combinacions possibles,
- * menys la que tots els moviments són a l'esquerra del número de combinacions
- * incials triat.
- */
-
-
-struct Map
-{
- char Cells[MAX_X][MAX_Y];
- int SizeX, SizeY;
- int ManX, ManY;
- int NumPlatforms;
- int NumBoxesInPlatform;
- char BoxMoved; // Boolean
-};
-
-
-
-void ReadMap(struct Map *M, char *FileName)
-{
- FILE *Fitxer;
- int i,j;
-
- if(!(Fitxer = fopen(FileName, "r")))
- {
- printf("Error opening %s!", FileName);
- exit(1);
- }
-
- M->SizeX=0;
- M->SizeY=0;
- while (!feof(Fitxer))
- {
- fgets(M->Cells[M->SizeY++], MAX_X, Fitxer);
- }
- M->SizeY--;
- M->SizeX = strlen(M->Cells[0]) - 1;
-
- M->NumPlatforms = 0;
- M->NumBoxesInPlatform = 0;
- for (j = 0; j<M->SizeY; j++)
- for (i=0; i<M->SizeX; i++)
- {
- if (M->Cells[j][i] == MAN)
- { M->ManX = i; M->ManY = j; }
- if (M->Cells[j][i] == PLATFORM)
- M->NumPlatforms++;
- else if (M->Cells[j][i] == BOXINPLATFORM)
- {
- M->NumPlatforms++;
- M->NumBoxesInPlatform++;
- } else if (M->Cells[j][i] != WALL)
- if ((M->Cells[j][i-1] == WALL &&
- M->Cells[j-1][i] == WALL) ||
- (M->Cells[j][i-1] == WALL &&
- M->Cells[j+1][i] == WALL) ||
- (M->Cells[j][i+1] == WALL &&
- M->Cells[j-1][i] == WALL) ||
- (M->Cells[j][i+1] == WALL &&
- M->Cells[j+1][i] == WALL))
- M->Cells[j][i] = CANTO;
- }
-
- M->Cells[M->ManY][M->ManX] = BLANK;
- M->BoxMoved = 0; // Needed?
-}
-
-
-void ShowMap (struct Map *M)
-{
- int i,j;
- for (j = 0; j<M->SizeY; j++)
- {
- for (i=0; i<M->SizeX; i++)
- printf("%c", M->Cells[j][i]);
- printf("\n");
- }
- printf("Man is at (%i,%i)\n", M->ManX, M->ManY);
- printf("Platforms: %i, BoxesInPlatform: %i\n", M->NumPlatforms,
- M->NumBoxesInPlatform);
-}
-
-
-
-void CopyMap (struct Map *Mdest, struct Map *Morig)
-{
- memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map));
-}
-
-int MoveMan (struct Map *M, int Direction)
-{
- int NewX, NewY;
-
-/*
- // Check if man is where it should be
- if (M->Cells[M->ManY][M->ManX] != MAN &&
- M->Cells[M->ManY][M->ManX] != MANINPLATFORM)
- {
- printf("Man isn't where it should be!\n");
- exit(2);
- }
-*/
-
- // Process Movement
- if (Direction == DIR_LEFT)
- { NewX = M->ManX - 1; NewY = M->ManY; }
- else if (Direction == DIR_RIGHT)
- { NewX = M->ManX + 1; NewY = M->ManY; }
- else if (Direction == DIR_UP)
- { NewX = M->ManX; NewY = M->ManY - 1; }
- else
- { NewX = M->ManX; NewY = M->ManY + 1; }
-
-
-
- // What's in front of the man?
-
- if (M->Cells[NewY][NewX] == WALL)
- {
- return MOVE_ILLEGAL; // ILLEGAL MOVE
- }
- else if (M->Cells[NewY][NewX] == BOX)
- {
- if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
- BLANK)
- {
- M->Cells[NewY][NewX] = BLANK;
- M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
- = BOX;
-
- M->ManX = NewX; M->ManY = NewY;
- M->BoxMoved = 1;
- return MOVE_BOX;
- }
- else
- if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
- PLATFORM)
- {
- M->Cells[NewY][NewX] = BLANK;
- M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
- = BOXINPLATFORM;
-
- M->ManX = NewX; M->ManY = NewY;
-
- M->NumBoxesInPlatform++;
- M->BoxMoved = 1;
- return MOVE_BOX;
- }
- else
- {
- return MOVE_ILLEGAL; // ILLEGAL MOVE
- }
- }else
- if (M->Cells[NewY][NewX] == BOXINPLATFORM)
- {
- if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
- BLANK)
- {
- M->Cells[NewY][NewX] = PLATFORM;
- M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
- = BOX;
-
- M->ManX = NewX; M->ManY = NewY;
- M->NumBoxesInPlatform--;
- M->BoxMoved = 1;
- return MOVE_BOX;
- }
- else
- if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
- PLATFORM)
- {
- M->Cells[NewY][NewX] = PLATFORM;
- M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
- = BOXINPLATFORM;
-
- M->ManX = NewX; M->ManY = NewY;
- M->BoxMoved = 1;
- return MOVE_BOX;
- }
- else
- {
- return MOVE_ILLEGAL; // ILLEGAL MOVE
- }
- }
- else
- {
- M->ManX = NewX; M->ManY = NewY;
- M->BoxMoved = 0;
- return MOVE_OK;
- }
-
- // Not Reachable
- return MOVE_ILLEGAL;
-}
-
-int InverseMove(char Dir1, char Dir2)
-{
- if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||
- (Dir1 + Dir2 == DIR_UP + DIR_DOWN))
- return 1;
- return 0;
-}
-
-int main(int argn, char **argv)
-{
- struct Map Morigin;
- struct Map M[MAX_MOVES+1];
- char Moves[MAX_MOVES];
- int NumMoves;
- int OldMaps;
- int IllegalMove;
- int Carry;
- int MoveResult;
-
- int i;
-
- if (argn != 3)
- {
- printf("Usage: %s <mapfile> <initial NumMoves>\n", argv[0]);
- exit(3);
- }
- ReadMap(&Morigin, argv[1]);
- sscanf(argv[2], "%i", &NumMoves);
-
- ShowMap(&Morigin);
-
- for (i = 0; i < NumMoves; i++)
- Moves[i] = DIR_LEFT;
-
- // Reget the original map
- CopyMap(&M[0], &Morigin);
- CopyMap(&M[NumMoves], &Morigin); // For the first while cond.
-
- IllegalMove = NumMoves - 1;
- // Process the combination
- for (i = 0; i < NumMoves; i++)
- {
- CopyMap(&M[i+1], &M[i]);
- if (!MoveMan(&M[i+1], Moves[i]))
- {
- IllegalMove = i;
- break;
- }
- }
-
- // Process the combinations.
- // Order: Left, Right, Up, Down
- while (M[NumMoves].NumPlatforms != M[NumMoves].NumBoxesInPlatform)
- {
- // Increase the Counter
- {
- Carry = 1;
- // Reset the direction of sure-invalid moves
- for (i = IllegalMove + 1; i < NumMoves; i++)
- Moves[i] = DIR_LEFT;
- // Increase Counter for a new try of moves
- for (i = IllegalMove; i >= 0 && Carry; i--)
- {
- Moves[i]++;
- Carry = 0;
- if (Moves[i] == DIR_DOWN + 1)
- { Moves[i] = DIR_LEFT; Carry = 1; }
- }
- OldMaps = i+1; // Sure? I think it's i+1
- // If we change the number of movements for solution
- if (Carry)
- {
- if (NumMoves > MAX_MOVES)
- break; // MAX MOVES EXCEEDED!!!
- NumMoves++;
- for (i = 0; i < NumMoves; i++)
- Moves[i] = DIR_LEFT;
- OldMaps=0;
- CopyMap(&M[NumMoves], &Morigin);
- // For the first while cond.
- printf("Provant %i moviments...\n", NumMoves);
- }
- }
-
-/*
- // Print the combination
-
- for (i=0; i < NumMoves; i++)
- {
- printf("%c", Moves[i]);
- }
- printf("\n");
-*/
-
- IllegalMove = NumMoves - 1;
- // Process the combination
- for (i = OldMaps; i < NumMoves - 1; i++)
- {
- CopyMap(&M[i+1], &M[i]);
- if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL)
- {
- IllegalMove = i;
- break;
- } else
- if (((Moves[i] + Moves[i-1] == DIR_LEFT + DIR_RIGHT) ||
- (Moves[i] + Moves[i-1] == DIR_UP + DIR_DOWN)) &&
- !M[i].BoxMoved)
- {
- IllegalMove = i;
- break;
- }
-
- }
- // Here i = NumMoves - 1
- CopyMap(&M[i+1], &M[i]);
- if (MoveMan(&M[i+1], Moves[i]) == MOVE_ILLEGAL)
- IllegalMove = i;
-
- }
-
- // Print the combination
- for (i=0; i < NumMoves; i++)
- {
- if (Moves[i] == DIR_LEFT)
- printf("L");
- else if (Moves[i] == DIR_RIGHT)
- printf("R");
- else if (Moves[i] == DIR_UP)
- printf("U");
- else if (Moves[i] == DIR_DOWN)
- printf("D");
- }
- printf("\n");
-
-/*
- // Print The Steps
- for (i=0; i < NumMoves; i++)
- {
- ShowMap(&M[i]);
- }
-*/
- return 0;
-
-}