/*
 *	118.c
 *
 *	Minghui Jiang	mjiang@cc.usu.edu
 *	Thu Oct 29 09:36:01 MDT 2009
 */

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

#define X	8	/* number of columns */
#define Y	10	/* number of rows */

#define K	4	/* maximum number of squares in a block */
#define N	6	/* number of blocks */

#define M	(N + 1)

typedef struct {
	int x;
	int y;
} s_coord;

typedef struct {
	s_coord squares[K];
	int k;
} s_block;

typedef struct state {
	s_coord dxdy[N];
	struct state *prev;	/* previous state */
	struct state *lnext;	/* next in list */
	struct state *hnext;	/* next in hashtable */
	int n;	/* the block that caused this state */
} s_state;

int squares[Y][X], squares_[Y][X] = {
	{ 0, 0, M, M, M, M, 0, 0 },
	{ 0, 0, M, 0, 0, M, 0, 0 },
	{ M, M, M, 0, 0, M, M, M },
	{ M, 0, 0, 0, 0, 0, 0, M },
	{ M, 0, 0, 0, 0, 0, 0, M },
	{ M, M, 0, 0, 0, 0, M, M },
	{ 0, M, 0, 0, 0, 0, M, 0 },
	{ 0, M, M, 0, 0, M, M, 0 },
	{ 0, 0, M, 0, 0, M, 0, 0 },
	{ 0, 0, M, M, M, M, 0, 0 },
};

const s_block blocks[N] = {
	{ { {2,4}, {3,4}, {3,5} }, 3 },
	{ { {4,4}, {5,4}, {4,5} }, 3 },
	{ { {2,5}, {2,6}, {3,6} }, 3 },
	{ { {5,5}, {4,6}, {5,6} }, 3 },
	{ { {3,7}, {4,7} }, 2 },
	{ { {3,1}, {4,1}, {3,2}, {4,2} }, 4 },
};

s_coord dxdy[N] = {
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},
	{0,0},	/* to goal */
};

const s_coord goal = {0,6};

int states = 0;

s_state **hashtable = NULL;
int hashtable_size = 0;
double hashcode_magic = 0.0;

void hashtable_init() {
    if ((hashtable = malloc(hashtable_size * sizeof(s_state *))) == NULL) {
        fprintf(stderr, "malloc error\n");
        exit(1);
    }
    memset(hashtable, 0, hashtable_size * sizeof(s_state *));
    hashcode_magic = (sqrt(5.0) - 1.0) / 2.0;
}

int hashcode(const s_coord *dxdy) {
    double f = 0.0;
	int n;

	for (n = 0; n < N; n++)
		f = ((f + dxdy[n].x) * hashcode_magic + dxdy[n].y) * hashcode_magic;
    if (f < 0.0)
        f = -f;
    return (int) (hashtable_size * f) % hashtable_size;
}

int hashtable_find(int n) {
    int i = hashcode(dxdy);
    s_state *state;

    for (state = hashtable[i]; state; state = state->hnext)
		if (state->n == n && !memcmp(state->dxdy, dxdy, N * sizeof(s_coord)))
			return 1;
    return 0;
}

void hashtable_insert(s_state *state) {
    int i = hashcode(state->dxdy);

    state->hnext = hashtable[i];
    hashtable[i] = state;
}

void list_append(s_state *state) {
	static s_state *tail = NULL;

	if (tail)
		tail->lnext = state;
	tail = state;
}

void init_squares() {
	int x, y;

	for (y = 0; y < Y; y++)
		for (x = 0; x < X; x++)
			squares[y][x] = squares_[y][x];
}

void mark_squares(int n, int z) {
	int k;

	for (k = 0; k < blocks[n].k; k++) {
		int x = blocks[n].squares[k].x + dxdy[n].x;
		int y = blocks[n].squares[k].y + dxdy[n].y;

		squares[y][x] = z;
	}
}

void print_squares(int step) {
	int x, y, n;

	printf("step %d\n", step);
	for (y = 0; y < Y; y++) {
		for (x = 0; x < X; x++)
			switch (n = squares[y][x]) {
			case 0:
				printf("  ");
				break;
			case M:
				printf("# ");
				break;
			default:
				printf("%d ", n);
			}
		printf("\n");
	}
}

s_state *alloc_state(s_state *prev, int n) {
	s_state *state;

	if ((state = malloc(sizeof(s_state))) == NULL) {
		fprintf(stderr, "malloc error\n");
		exit(1);
	}
	memcpy(state->dxdy, dxdy, N * sizeof(s_coord));
	state->prev = prev;
	state->lnext = NULL;
	state->hnext = NULL;
	state->n = n;
	if (prev && state->n == prev->n)
		state->prev = prev->prev;
	list_append(state);
	hashtable_insert(state);
	states++;
	return state;
}

void load_state(s_state *state) {
	int n;

	memcpy(dxdy, state->dxdy, N * sizeof(s_coord));
	init_squares();
	for (n = 0; n < N; n++)
		mark_squares(n, n + 1);
}

int print_state(s_state *state) {
	if (state->prev == NULL)
		return 0;
	else {
		int steps = print_state(state->prev);

		load_state(state);
		printf("\n");
		print_squares(++steps);
		return steps;
	}
}

void check_state(s_state *state) {
	if (state->dxdy[N - 1].x == goal.x && state->dxdy[N - 1].y == goal.y) {
		int steps = print_state(state);

		printf("\n%d steps among %d states\n", steps, states);
		exit(0);
	}
}

s_state *next_state_n_d(s_state *prev, int n, int d) {
	s_state *next;
	int k;

	load_state(prev);
	mark_squares(n, 0);
	switch (d) {
	case 1:
		dxdy[n].x += 1;
		break;
	case 2:
		dxdy[n].y += 1;
		break;
	case 3:
		dxdy[n].x -= 1;
		break;
	case 4:
		dxdy[n].y -= 1;
		break;
	}
	for (k = 0; k < blocks[n].k; k++) {
		int x = blocks[n].squares[k].x + dxdy[n].x;
		int y = blocks[n].squares[k].y + dxdy[n].y;

		if (squares[y][x])
			return NULL;
	}
	if (hashtable_find(n))
		return NULL;

	next = alloc_state(prev, n);
	check_state(next);
	return next;
}

s_state *next_state_n(s_state *prev, int n) {
	s_state *more = NULL;
	int d;

	for (d = 1; d <= 4; d++) {
		s_state *next = next_state_n_d(prev, n, d);

		if (next != NULL && more == NULL)
			more = next;
	}
	return more;
}

int main(int argc, char *argv[]) {
	s_state *state;

	if (argc >= 2)
		hashtable_size = atoi(argv[1]);
	if (hashtable_size <= 0)
		hashtable_size = 200000;
	hashtable_init();

	state = alloc_state(NULL, N);
	load_state(state);
	print_squares(0);
	while (state) {
		int n;

		for (n = 0; n < N; n++) {
			s_state *more;

			if (state->n == n)
				continue;

			for (more = next_state_n(state, n); more; more = more->lnext)
				next_state_n(more, n);
		}
		state = state->lnext;
	}
	printf("\nno solution among %d states\n", states);
	return 0;
}