#include <stdio.h>
#include <string.h>

#define BOX '*'
#define WALL '#'
#define MAN '8'
#define PLATFORM '+'
#define BOXINPLATFORM 'O'
#define MANINPLATFORM 'E'
#define BLANK ' '

#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

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



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; }
			else if (M->Cells[j][i] == PLATFORM)
				M->NumPlatforms++;
			else if (M->Cells[j][i] == BOXINPLATFORM)
			{
				M->NumPlatforms++;
				M->NumBoxesInPlatform++;
			}
		}
}


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 0;	// ILLEGAL MOVE
	}
	else if (M->Cells[NewY][NewX] == BOX)
	{
		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
			BLANK)
		{
			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
				= BOX;

			if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
			{	// Man is over Platform
				M->Cells[M->ManY][M->ManX] = PLATFORM;
				M->Cells[NewY][NewX] = MAN;
			}
			else	// Man is over Blank
			{
				M->Cells[M->ManY][M->ManX] = BLANK;
				M->Cells[NewY][NewX] = MAN;
			}
			M->ManX = NewX; M->ManY = NewY;
			return 1;
		}
		else
		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
				PLATFORM)
		{
			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
				= BOXINPLATFORM;

			if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
			{	// Man is over Platform
				M->Cells[M->ManY][M->ManX] = PLATFORM;
				M->Cells[NewY][NewX] = MAN;
			}
			else	// Man is over Blank
			{
				M->Cells[M->ManY][M->ManX] = BLANK;
				M->Cells[NewY][NewX] = MAN;
			}
			M->ManX = NewX; M->ManY = NewY;

			M->NumBoxesInPlatform++;
			return 1;
		}
		else
		{
			return 0;	// ILLEGAL MOVE
		}
	}else
	if (M->Cells[NewY][NewX] == BOXINPLATFORM)
	{
		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
			BLANK)
		{
			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
				= BOX;

			if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
			{	// Man is over Platform
				M->Cells[M->ManY][M->ManX] = PLATFORM;
				M->Cells[NewY][NewX] = MANINPLATFORM;
			}
			else	// Man is over Blank
			{
				M->Cells[M->ManY][M->ManX] = BLANK;
				M->Cells[NewY][NewX] = MANINPLATFORM;
			}
			M->ManX = NewX; M->ManY = NewY;
			M->NumBoxesInPlatform--;
			return 1;
		}
		else
		if (M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)] ==
				PLATFORM)
		{
			M->Cells[NewY + (NewY-M->ManY)][NewX + (NewX-M->ManX)]
				= BOXINPLATFORM;

			if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
			{	// Man is over Platform
				M->Cells[M->ManY][M->ManX] = PLATFORM;
				M->Cells[NewY][NewX] = MANINPLATFORM;
			}
			else	// Man is over Blank
			{
				M->Cells[M->ManY][M->ManX] = BLANK;
				M->Cells[NewY][NewX] = MANINPLATFORM;
			}
			M->ManX = NewX; M->ManY = NewY;
			return 1;
		}
		else
		{
			return 0;	// ILLEGAL MOVE
		}
	}
	else if (M->Cells[NewY][NewX] == PLATFORM)
	{
		if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
		{	// Man is over Platform
			M->Cells[M->ManY][M->ManX] = PLATFORM;
			M->Cells[NewY][NewX] = MANINPLATFORM;
		}
		else	// Man is over Blank
		{
			M->Cells[M->ManY][M->ManX] = BLANK;
			M->Cells[NewY][NewX] = MANINPLATFORM;
		}
		M->ManX = NewX; M->ManY = NewY;
		return 1;
	}
	else if (M->Cells[NewY][NewX] == BLANK)		// IF not needed
	{
		if (M->Cells[M->ManY][M->ManX] == MANINPLATFORM)
		{	// Man is over Platform
			M->Cells[M->ManY][M->ManX] = PLATFORM;
			M->Cells[NewY][NewX] = MAN;
		}
		else	// Man is over Blank
		{
			M->Cells[M->ManY][M->ManX] = BLANK;
			M->Cells[NewY][NewX] = MAN;
		}
		M->ManX = NewX; M->ManY = NewY;
		return 1;
	}
	return 1;
}

int main()
{
	struct Map Morigin;
	struct Map M[MAX_MOVES+1];
	char Moves[MAX_MOVES];
	int NumMoves;
	int OldMaps;
	int IllegalMove;
	int Carry;

	int i;

	ReadMap(&Morigin, "model");

	ShowMap(&Morigin);

	printf("Numero de moviments inicials a provar: ");
	scanf("%i", &NumMoves);
	IllegalMove = NumMoves - 1;

	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; i++)
		{
			CopyMap(&M[i+1], &M[i]);
			if (!MoveMan(&M[i+1], Moves[i]))
			{
				IllegalMove = i;
				break;
			}
		}
					
	}

	// Print the combination
	for (i=0; i < NumMoves; i++)
	{
		printf("%c", Moves[i]);
	}
	printf("\n");

/*
	// Print The Steps
	strcpy(Moves, "DDDRUU");

	for (i=0; i < 6; i++)
	{
		printf("%i", MoveMan(&M, Moves[i]));
		ShowMap(&M);
	}
*/
	return 0;

}