#include <stdio.h>

#include <string.h>

#define BOX '$'

#define WALL '#'

#define MAN '@'

#define PLATFORM '.'

#define BOXINPLATFORM '*'

#define MANINPLATFORM 'E'

#define BLANK ' '

#define CANTO '-'

#define MANCANMOVE '+'

#define NBOX(n) ((n)<<2)

#define DIR_LEFT 0

#define DIR_RIGHT 1

#define DIR_UP 2

#define DIR_DOWN 3

#define MAX_X 50

#define MAX_Y 50

#define MAX_MOVES 50

#define MAX_MANMOVES 50

#define MAX_BOXES 15

#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.

 * 13/01/2002

 * Comentari afegit el 4/01/2003:

 * Cerca la solució segons el moviment de caixes, i no el de l'home.

 * Falta optimitzar: Llocs on no posar caixes segons les caixes (són dinàmics

 * segons cada element de l'array de mapes!)

 *

 * Diria que el programa no es deixa cap branca de l'arbre de backtracking

 */

struct Map

{

	char Cells[MAX_Y][MAX_X];

	char ManMoves[MAX_Y][MAX_X];

	int SizeX, SizeY;

	int ManX, ManY;

	int NumPlatforms;

	int NumBoxesInPlatform;

	int BoxX[MAX_BOXES];

	int BoxY[MAX_BOXES];

	int NumBoxes;

};

void CopyMap (struct Map *Mdest, struct Map *Morig)

{

	memcpy((void *) Mdest, (void *) Morig, sizeof (struct Map));

}

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->SizeY--;

	M->SizeX = strlen(M->Cells[0]) - 1;

	M->NumPlatforms = 0;

	M->NumBoxesInPlatform = 0;

	M->NumBoxes = 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; 

				M->Cells[M->ManY][M->ManX] = BLANK;

			}

			if (M->Cells[j][i] == PLATFORM)

				M->NumPlatforms++;

			else if (M->Cells[j][i] == BOXINPLATFORM)

			{

				M->Cells[j][i] = PLATFORM;

				M->NumPlatforms++;

				M->NumBoxesInPlatform++;

				M->BoxX[M->NumBoxes] = i;

				M->BoxY[M->NumBoxes] = j;

				M->NumBoxes++;

			} else if (M->Cells[j][i] == BOX)

			{

				M->Cells[j][i] = BLANK;

				M->BoxX[M->NumBoxes] = i;

				M->BoxY[M->NumBoxes] = j;

				M->NumBoxes++;

			} 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;

			}

		}

	if(M->NumBoxes > M->NumPlatforms)

	{

		printf("More boxes than platforms!\n");

		exit(2);

	}

}

void ShowMap (struct Map *M)

{

	struct Map Temp;

	int i,j;

	CopyMap(&Temp, M);

	Temp.Cells[Temp.ManY][Temp.ManX] = MAN;

	for (i = 0; i < Temp.NumBoxes; i++)

	{

		if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == BLANK)

			Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOX;

		else if (Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] == PLATFORM)

			Temp.Cells[Temp.BoxY[i]][Temp.BoxX[i]] = BOXINPLATFORM;

	}

	for (j = 0; j<Temp.SizeY; j++)

	{

		for (i=0; i<Temp.SizeX; i++)

			printf("%c", Temp.Cells[j][i]);

		printf("\n");

	}

	// Print Where the man can move

	for (j = 0; j<Temp.SizeY; j++)

	{

		for (i=0; i<Temp.SizeX; i++)

			printf("%c", Temp.ManMoves[j][i]);

		printf("\n");

	}

	printf("Man is at (%i,%i)\n", Temp.ManX, Temp.ManY);

	printf("Platforms: %i, BoxesInPlatform: %i\n", Temp.NumPlatforms,

			Temp.NumBoxesInPlatform);

}

int InverseMove(char Dir1, char Dir2)

{

	if ((Dir1 + Dir2 == DIR_LEFT + DIR_RIGHT) ||

		(Dir1 + Dir2 == DIR_UP + DIR_DOWN))

		return 1;

	return 0;

}

void GetManMoves(struct Map *M)

{

	int X[MAX_MANMOVES], Y[MAX_MANMOVES];

	int NewX[MAX_MANMOVES], NewY[MAX_MANMOVES];

	int NumMoves, NewMoves;

	int j, i;

	NumMoves = 1;

	for (j = 0; j<M->SizeY; j++)

		for (i=0; i<M->SizeX; i++)

			M->ManMoves[j][i] = (M->Cells[j][i] == WALL)?WALL:BLANK;

	for (i = 0; i<M->NumBoxes; i++)

		M->ManMoves[M->BoxY[i]][M->BoxX[i]] = WALL;

	NewMoves = 1;

	NewX[0] = M->ManX;

	NewY[0] = M->ManY;

	M->ManMoves[M->ManY][M->ManX] = MANCANMOVE;

	while (NewMoves)

	{

		NumMoves = NewMoves;

		for (i=0; i<NewMoves; i++)

		{

			X[i] = NewX[i];

			Y[i] = NewY[i];

		}

		NewMoves = 0;

		for (i=0; i<NumMoves; i++)

		{

			if(M->ManMoves[Y[i]][X[i]-1] == BLANK)

			{

				NewX[NewMoves] = X[i]-1;

				NewY[NewMoves] = Y[i];

				M->ManMoves[Y[i]][X[i]-1] = MANCANMOVE;

				NewMoves++;

			}

			if(M->ManMoves[Y[i]][X[i]+1] == BLANK)

			{

				NewX[NewMoves] = X[i]+1;

				NewY[NewMoves] = Y[i];

				M->ManMoves[Y[i]][X[i]+1] = MANCANMOVE;

				NewMoves++;

			}

			if(M->ManMoves[Y[i]-1][X[i]] == BLANK)

			{

				NewX[NewMoves] = X[i];

				NewY[NewMoves] = Y[i]-1;

				M->ManMoves[Y[i]-1][X[i]] = MANCANMOVE;

				NewMoves++;

			}

			if(M->ManMoves[Y[i]+1][X[i]] == BLANK)

			{

				NewX[NewMoves] = X[i];

				NewY[NewMoves] = Y[i]+1;

				M->ManMoves[Y[i]+1][X[i]] = MANCANMOVE;

				NewMoves++;

			}

		}

	}

}

/* Returns bool */

char IsStupidPos(struct Map *M, int X, int Y)

{

	struct Map MTemp;

	int NumBoxes, NumWalls, NumBoxesInPlatform;

	int j, i;

	CopyMap(&MTemp, M);

	for (i = 0; i<MTemp.NumBoxes; i++)

		if (MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] == PLATFORM)

			MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] =

			BOXINPLATFORM;

		else

			MTemp.Cells[MTemp.BoxY[i]][MTemp.BoxX[i]] = BOX;

//	ShowMap(&MTemp);

	/* We don't verify if j<=Y or i<=X is outside the map. It shouldn't

	 * be, as it will be called with X,Y pair beeing the coordinates of a

	 * Box!

	 */

	for (j = Y-1; j<=Y; j++)

		for (i=X-1; i<=X; i++)

		{

			NumBoxes = NumWalls = NumBoxesInPlatform = 0;

			/* Up-Left Cell */

			if (MTemp.Cells[j][i] == WALL)

				NumWalls++;

			else if (MTemp.Cells[j][i] == BOX)

				NumBoxes++;

			else if (MTemp.Cells[j][i] == BOXINPLATFORM)

				NumBoxesInPlatform++;

			/* Up-Right Cell */

			if (MTemp.Cells[j][i+1] == WALL)

				NumWalls++;

			else if (MTemp.Cells[j][i+1] == BOX)

				NumBoxes++;

			else if (MTemp.Cells[j][i+1] == BOXINPLATFORM)

				NumBoxesInPlatform++;

			/* Down-Right Cell */

			if (MTemp.Cells[j+1][i+1] == WALL)

				NumWalls++;

			else if (MTemp.Cells[j+1][i+1] == BOX)

				NumBoxes++;

			else if (MTemp.Cells[j+1][i+1] == BOXINPLATFORM)

				NumBoxesInPlatform++;

			/* Down-Left Cell */

			if (MTemp.Cells[j+1][i] == WALL)

				NumWalls++;

			else if (MTemp.Cells[j+1][i] == BOX)

				NumBoxes++;

			else if (MTemp.Cells[j+1][i] == BOXINPLATFORM)

				NumBoxesInPlatform++;

			if ((NumBoxesInPlatform + NumBoxes + NumWalls == 4) &&

				(NumBoxes >= 1)) 

				return MOVE_ILLEGAL;

		}

	return MOVE_OK;

}

int MoveBox(struct Map *M, int NumBox, int Direction)

{

	char InPlatform;

	InPlatform = (M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] == PLATFORM);

	switch(Direction)

	{

		case DIR_LEFT:

			if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] ==

				MANCANMOVE &&

				(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1]

				!= WALL) &&

				(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]-1]

				!= CANTO) )

			{

				if(InPlatform)

					M->NumBoxesInPlatform--;

				M->BoxX[NumBox]--;

				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==

					PLATFORM)

					M->NumBoxesInPlatform++;

				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);

			}else return 0;

			break;

		case DIR_RIGHT:

			if(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]-1] ==

				MANCANMOVE &&

				(M->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1]

				!= WALL) &&

				(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]+1]

				!= CANTO) )

			{

				if(InPlatform)

					M->NumBoxesInPlatform--;

				M->BoxX[NumBox]++;

				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==

					PLATFORM)

					M->NumBoxesInPlatform++;

				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);

			}else return 0;

			break;

		case DIR_UP:

			if(M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] ==

				MANCANMOVE &&

				(M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]]

				!= WALL) &&

				(M->Cells[M->BoxY[NumBox]-1][M->BoxX[NumBox]]

				!= CANTO) )

			{

				if(InPlatform)

					M->NumBoxesInPlatform--;

				M->BoxY[NumBox]--;

				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==

					PLATFORM)

					M->NumBoxesInPlatform++;

				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);

			}else return 0;

			break;

		case DIR_DOWN:

			if(M->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] ==

				MANCANMOVE &&

				(M->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]]

				!= WALL) &&

				(M->Cells[M->BoxY[NumBox]+1][M->BoxX[NumBox]]

				!= CANTO) )

			{

				if(InPlatform)

					M->NumBoxesInPlatform--;

				M->BoxY[NumBox]++;

				if(M->Cells[M->BoxY[NumBox]][M->BoxX[NumBox]] ==

					PLATFORM)

					M->NumBoxesInPlatform++;

				return IsStupidPos(M,M->BoxX[NumBox], M->BoxY[NumBox]);

			}else return 0;

			break;

	}

	/* Check for stupid movement */

	return 0;

}

void PrintCombination(int Moves[], int NumMoves)

{

	int i;

	for (i=0; i < NumMoves; i++)

	{

		printf("%i", Moves[i] >> 2);

		if ((Moves[i] & 0x03) == DIR_LEFT)

			printf("L");

		else if ((Moves[i] & 0x03) == DIR_RIGHT)

			printf("R");

		else if ((Moves[i] & 0x03) == DIR_UP)

			printf("U");

		else

			printf("D");

		printf(",");

	}

	printf("\n");

}

int main(int argn, char **argv)

{

	struct Map Morigin;

	struct Map M[MAX_MOVES+1];

	int Moves[MAX_MOVES];

	int NumMoves;

	int OldMaps;

	int IllegalMove;

	int Carry;

	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] = NBOX(0) + DIR_LEFT;

	// Reget the original map

	CopyMap(&M[0], &Morigin);

	CopyMap(&M[NumMoves], &Morigin);	// For the first while cond.

	GetManMoves(&M[0]);

	ShowMap(&M[0]);

	IllegalMove = NumMoves - 1;

	// Process the combination

	for (i = 0; i < NumMoves; i++)

	{

		CopyMap(&M[i+1], &M[i]);

		if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03))

		{

			IllegalMove = i;

			break;

		}

	}

	// Main solution finder loop

	while (!(M[NumMoves].NumPlatforms == M[NumMoves].NumBoxesInPlatform && 

	IllegalMove == -1))

	{

		// Increase the Counter

		{

			Carry = 1;

			// If last combination was legal

			if (IllegalMove == -1)

				IllegalMove = NumMoves -1;

			// Reset the direction of sure-invalid moves

			for (i = IllegalMove + 1; i < NumMoves; i++)

				Moves[i] = NBOX(0) + DIR_LEFT;

			// Increase Counter for a new try of moves

			for (i = IllegalMove; i >= 0 && Carry; i--)

			{

				Moves[i]++;

				Carry = 0;

				if (Moves[i] ==NBOX(M[0].NumBoxes-1)+DIR_DOWN+1)

				{ Moves[i] = NBOX(0) + 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] = NBOX(0) + DIR_LEFT;

				OldMaps=0;

				CopyMap(&M[NumMoves], &Morigin);

					// For the first while cond.

				printf("Provant %i moviments...\n", NumMoves);

				fflush(stdout);

			}

		}

		// First assume combination is legal

		IllegalMove = -1;

		// Process the combination

		for (i = OldMaps; i < NumMoves - 1; i++)

		{

			CopyMap(&M[i+1], &M[i]);

			if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03))

			{

				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;

			}*/

			// For next map:

			GetManMoves(&M[i+1]);

		}

		// Here i = NumMoves - 1

		CopyMap(&M[i+1], &M[i]);

		if (!MoveBox(&M[i+1], Moves[i]>>2, Moves[i] & 0x03))

			IllegalMove = i;

		//ShowMap(&M[i+1]);

		//printf("IM: %i\n", IllegalMove);