#include <stdio.h>

#include <string.h>

#include <assert.h>

#include <stdlib.h>

#include <unistd.h>

#include <signal.h>

#define BOX '$'

#define WALL '#'

#define MAN '@'

#define PLATFORM '.'

#define BOXINPLATFORM '*'

#define MANINPLATFORM 'E'

#define BLANK ' '

#define CORNER '-'

#define MANCANMOVE '+'

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

//#define DEBUG

enum

{

	ALARM_SECONDS=1

};

enum logic

{

	TRUE=1,

	FALSE=0,

};

#define MAX_X 50

#define MAX_Y 50

#define MAX_MOVES 50

#define MAX_STEPS 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 Position

{

	int x;

	int y;

};

struct Map

{

	char Cells[MAX_Y][MAX_X];

	char cells_boxes[MAX_Y][MAX_X];

	char man_moves[MAX_Y][MAX_X];

	int SizeX, SizeY;

	struct Position Man;

	int NumPlatforms;

	int NumBoxesInPlatform;

	struct Position Box[MAX_BOXES];

	int NumBoxes;

};

enum e_direction

{

	DIR_LEFT,

	DIR_RIGHT,

	DIR_DOWN,

	DIR_UP

};

const struct Position move_vectors[4] = {

	{0, 1},

	{0, -1},

	{1, 0},

	{-1, 0}};

struct BoxMove

{

	int box;

	struct Position dir;

};

float percent_to_show = 0;

int depth_to_show = 0;

int max_depth = 0;

int min_depth_period = 0;

int max_depth_period = 0;

struct Map * actual_map;

void CopyMap (struct Map *Mdest, const 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->Man.x = i; M->Man.y = j; 

				M->Cells[M->Man.y][M->Man.x] = 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->Box[M->NumBoxes].x = i;

				M->Box[M->NumBoxes].y = j;

				M->NumBoxes++;

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

			{

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

				M->Box[M->NumBoxes].x = i;

				M->Box[M->NumBoxes].y = j;

				M->NumBoxes++;

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

			{

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

			} 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] = CORNER;

			}

		}

}

void ShowMap (const struct Map *M)

{

	struct Map Temp;

	int i,j;

	CopyMap(&Temp, M);

	Temp.Cells[Temp.Man.y][Temp.Man.x] = MAN;

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

	{

		if (Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] == PLATFORM)

			Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] =BOXINPLATFORM;

		else

			Temp.Cells[Temp.Box[i].y][Temp.Box[i].x] = BOX;

	}

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

	{

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

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

		fprintf(stderr,"\n");

	}

#if 0

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

	}

#endif

	printf("Man is at (%i,%i)\n", Temp.Man.x, Temp.Man.y);

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

}

#if 0 /*** THIS IS AN ERROR!!!  The box_will_be_blocked function doesn't work!*/

 Situation:

  ->@$ #

      $

*/

int box_will_be_blocked(const struct Map * m, const struct Position mov,

	const struct Position box_pos)

{

	struct Position next_pos2, tmp, tmp2[2];

	int i;

	next_pos2.x = box_pos.x + mov.x;

	next_pos2.y = box_pos.y + mov.y;

	tmp.x = next_pos2.x + mov.x;

	tmp.y = next_pos2.y + mov.y;

	tmp2[0].x = next_pos2.x + mov.y;

	tmp2[0].y = next_pos2.y + mov.x;

	tmp2[1].x = next_pos2.x - mov.y;

	tmp2[1].y = next_pos2.y - mov.x;

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

	{

		if (m->man_moves[tmp.y][tmp.x] == WALL &&

			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)

		{

			return TRUE;

		}

		else if (m->man_moves[tmp.y][tmp.x] == BOX &&

			m->man_moves[tmp2[i].y][tmp2[i].x] == WALL)

		{

			return TRUE;

		}

		else if (m->man_moves[tmp.y][tmp.x] == BOX &&

			m->man_moves[tmp2[i].y][tmp2[i].x] == BOX)

		{

			return TRUE;

		}

	}

	return FALSE;

}

int is_corner_area(const struct Map * m, const struct Position p,

	const struct Position box, const struct Position new_box)

{

	int NumMoves, NewMoves;

	struct Position pos[MAX_MOVES];

	struct Position new_pos[MAX_MOVES];

	char corners[MAX_Y][MAX_X];

	int i,j;

	struct Position next_pos;

	char *next_cell;

	/* Blank the garden */

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

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

			corners[j][i] = m->Cells[j][i];

	/* Let's put the boxes */

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

		corners[m->Box[i].y][m->Box[i].x] = BOX;

	/* Let's put our box - it can be simply added */

	corners[new_box.y][new_box.x] = BOX;

	/* Let's remove the original box. */

	corners[box.y][box.x] = BLANK;

	NewMoves = 1;

	new_pos[0] = p;

	while (NewMoves > 0)

	{

		/* The before named "New Moves" become the moves we have

		   to analyze */

		NumMoves = NewMoves;

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

		{

			pos[i] = new_pos[i];

		}

		/* Search new positions for each position */

		NewMoves = 0;

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

		{

			/* For each direction */

			for (j=0; j<4; j++)

			{

				next_pos.x = pos[i].x + move_vectors[j].x;

				next_pos.y = pos[i].y + move_vectors[j].y;

				next_cell = &corners[next_pos.y][next_pos.x];

				if(*next_cell == BLANK ||

					*next_cell == PLATFORM)

				{

					return FALSE;

				}

				else if(*next_cell == CORNER)

				{

					new_pos[NewMoves] = next_pos;

					*next_cell = MANCANMOVE;

					NewMoves++;

				}

			}

		}

	}

	return TRUE;

}

int does_box_close_corners(const struct Map * m, const struct Position mov,

	const struct Position box_pos)

{

	struct Position p, p2;

	p.x = box_pos.x + mov.x;

	p.y = box_pos.y + mov.y;

	/* Let's plan the checks */

	/* The point will be marked with a MANCANMOVE */

	p2.x = p.x + mov.x;

	p2.y = p.y + mov.y;

	if (m->Cells[p2.y][p2.x] == CORNER)

	{

		if (is_corner_area(m, p2, box_pos, p))

			return TRUE;

	}

	p2.x = p.x + mov.y;

	p2.y = p.y + mov.x;

	if (m->Cells[p2.y][p2.x] == CORNER)

	{

		if (is_corner_area(m, p2, box_pos, p))

			return TRUE;

	}

	p2.x = p.x - mov.y;

	p2.y = p.y - mov.x;

	if (m->Cells[p2.y][p2.x] == CORNER)

	{

		if (is_corner_area(m, p2, box_pos, p))

			return TRUE;

	}

	return FALSE;

}

#endif

/*

Catch the situation where a box is moved next to a corner, where the box

next to it will not be able to be moved.

*/

int is_dead1(const struct Map * m, const struct Position mov,

	const struct Position new_pos)

{

	struct Position opposite1, opposite2;

	/* The wall corners must exist */

	opposite1.x = -mov.y;

	opposite1.y = -mov.x;

	opposite2.x = mov.y;

	opposite2.y = mov.x;

#ifdef DEBUG

	ShowMap(m);

#endif

	/* Test the first corner */

	if (m->Cells[new_pos.y+mov.y+opposite1.y][new_pos.x+mov.x+opposite1.x]

		== WALL)

	{

		/* Test wall at opposites 1*/

		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

			== WALL &&

			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

		{

				return TRUE;

		}

		else

		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

			== BOX &&

			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

		{

				return TRUE;

		}

		/* Test wall at opposites 2 */

		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

			== WALL &&

			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

		{

				return TRUE;

		}

		else

		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

			== BOX &&

			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

		{

				return TRUE;

		}

	}

	/* Test the second corner */

	if (m->Cells[new_pos.y+mov.y+opposite2.y][new_pos.x+mov.x+opposite2.x]

		== WALL)

	{

		/* Test wall at opposites 1*/

		if (m->Cells[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

			== WALL &&

			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

		{

				return TRUE;

		}

		else

		if (m->man_moves[new_pos.y+opposite1.y][new_pos.x+opposite1.x]

			== BOX &&

			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

		{

				return TRUE;

		}

		/* Test wall at opposites 2 */

		if (m->Cells[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

			== WALL &&

			m->man_moves[new_pos.y+mov.y][new_pos.x+mov.x] == BOX)

		{

				return TRUE;

		}

		else

		if (m->man_moves[new_pos.y+opposite2.y][new_pos.x+opposite2.x]

			== BOX &&

			m->Cells[new_pos.y+mov.y][new_pos.x+mov.x] == WALL)

		{

				return TRUE;

		}

	}

	return FALSE;

}

/*

Catch the situation where a corner gets surrounded by boxes.

*/

int is_dead2(const struct Map * m, const struct Position mov,

	const struct Position new_pos)

{

	struct Position next, next2, opposite1, opposite2;

	next.x = new_pos.x+mov.x;

	next.y = new_pos.y+mov.y;

	/* The corner must exist */

	if (m->Cells[next.y][next.x] != CORNER)

		return FALSE;

	/* The wall corners must exist */

	opposite1.x = next.x -mov.y;

	opposite1.y = next.y -mov.x;

	opposite2.x = next.x + mov.y;

	opposite2.y = next.y + mov.x;

	if (m->man_moves[opposite1.y][opposite1.x] == BOX)

	{

		if(m->Cells[opposite1.y+mov.y][opposite1.x+mov.x] == WALL

		   && m->Cells[opposite1.y-mov.y][opposite1.x-mov.x] == WALL)

		   return TRUE;

	}

	if (m->man_moves[opposite2.y][opposite2.x] == BOX)

	{