#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_BOXES 15

#define MOVE_OK		1

#define MOVE_BOX	2

#define MOVE_ILLEGAL	0

/* SOKOBAN Solution Finder

 *

 * Input File Format: XSB

 *

 * XSB Format definition:

 * 	Character matrix of:

 * 		@	MAN

 * 		#	WALL

 * 		$	BOX

 * 		*	BOX over PLATFORM

 * 		+	PLATFORM

 * 		-	(optional) Where a BOX should not be put

 * 	Everything that cannot be reached by the man or boxes (WALLS) must be

 * 	marked as is: WALLS.

 * 	All lines must be of the same length.

 */

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;

			}

		}

}

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]] == PLATFORM)

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

		else

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

	}

	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_MOVES], Y[MAX_MOVES];

	int NewX[MAX_MOVES], NewY[MAX_MOVES];

	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;

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

			}

		}

	}

}

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)

			{

				M->ManX = M->BoxX[NumBox];

				M->ManY = M->BoxY[NumBox];

				if(InPlatform)

					M->NumBoxesInPlatform--;

				M->BoxX[NumBox]--;

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

					PLATFORM)

					M->NumBoxesInPlatform++;

				return 1;

			}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->ManMoves[M->BoxY[NumBox]][M->BoxX[NumBox]+1] !=

				CANTO)

			{

				M->ManX = M->BoxX[NumBox];

				M->ManY = M->BoxY[NumBox];

				if(InPlatform)

					M->NumBoxesInPlatform--;

				M->BoxX[NumBox]++;

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

					PLATFORM)

					M->NumBoxesInPlatform++;

				return 1;

			}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->ManMoves[M->BoxY[NumBox]-1][M->BoxX[NumBox]] !=

				CANTO)

			{

				M->ManX = M->BoxX[NumBox];

				M->ManY = M->BoxY[NumBox];

				if(InPlatform)

					M->NumBoxesInPlatform--;

				M->BoxY[NumBox]--;

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

					PLATFORM)

					M->NumBoxesInPlatform++;

				return 1;

			}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->ManMoves[M->BoxY[NumBox]+1][M->BoxX[NumBox]] !=

				CANTO)

			{

				M->ManX = M->BoxX[NumBox];

				M->ManY = M->BoxY[NumBox];

				if(InPlatform)

					M->NumBoxesInPlatform--;

				M->BoxY[NumBox]++;

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

					PLATFORM)

					M->NumBoxesInPlatform++;

				return 1;

			}else return 0;

			break;

	}

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

	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;

		}

		GetManMoves(&M[i+1]);

	}

	// Main solution finder loop

	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] = 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);

			}

		}

		// Print the combination

//		PrintCombination(Moves, NumMoves);

		IllegalMove = NumMoves - 1;

		// Process the combination

//		printf("------- STARTING COMBINATION ------------\n");

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

		{

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

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

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

			{

				IllegalMove = i;

				break;

			}/* else	// Si el moviment es bo

			if ((Moves[i] >> 2) == (Moves[i+1] >> 2) &&

				((Moves[i] & 0x03) + (Moves[i+1] & 0x03) == 1||

				((Moves[i] & 0x03) + (Moves[i+1] & 0x03) == 5)))

			{

				IllegalMove = i;

				break;

			}*/

			GetManMoves(&M[i+1]);

//			ShowMap(&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;

/*

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

		{

			ShowMap(&M[i+1]);

		}

*/

	}

	// Print the combination

	PrintCombination(Moves, NumMoves);

/*

	// Print The Steps

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

	{

		ShowMap(&M[i]);

	}

*/

	return 0;

}