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

}