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

}