/* Sorry, BSD for alloca(). */

#define _BSD_SOURCE

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

#define HTAB_SIZE 56783

/* #define STSTEP 100 */
/* #undef NDEBUG */
/* #define BENCHMARK */

typedef char stt[20];
#define SaXYL(x,y) ((x)+(y)*5)
#define SaLX(l) ((l)%5)
#define SaLY(l) ((l)/5)
#define SaLXY(l,x,y) do { (x)=SaLX((l)); (y)=SaLY((l)); } while (0)

unsigned total=0,solutions=0;
#ifdef STSTEP
unsigned gone=0;
#endif

stt init=
	"{}{}#"
	"AB^#+"
	"CDv#+"
	"{}{}#";

struct st {
	struct st *nexttogo,*nextinchain,*ost;
	stt data;
	} *togo,**togop=&togo,*togonow,*htab[HTAB_SIZE];
int level=-1;

static void chk(void *p)
{
	if (p) return;
	fprintf(stderr,"Virtual memory exhausted!\n");
	exit(EXIT_FAILURE);
}
#define chknew(a) chk((a)=malloc(sizeof(*(a))))

static unsigned hash(const char *st)
{
unsigned r=7;
unsigned char i;

	for (i=0;i<20;i++)
		r=r*13+(*st++);
	return r%HTAB_SIZE;
}

static struct st **findhash(const char *st,unsigned hval)
{
struct st **r;
	for (r=&htab[hval];*r;r=&(*r)->nextinchain)
		if (!memcmp((*r)->data,st,20)) break;
	return r;
}

static void dumpst(const char *st)
{
unsigned char yi;

	for (yi=0;yi<4;yi++)
		printf("  | %.5s |\n",st+SaXYL(0,yi));
	puts("  \\-------/");
}

static void addstate(const char *st,struct st *ost)
{
struct st *now,**nowp;
unsigned hval;

	hval=hash(st);
	if (*(nowp=findhash(st,hval))) return;
#ifndef NDEBUG
	if (ost) {
		puts("***addstate:");
		dumpst(st);
		}
#endif
	chk(now=malloc(sizeof(*now)));
	*togop=now;togop=&now->nexttogo; now->nexttogo=NULL;
	now->nextinchain=NULL; *nowp=now;
	memcpy(now->data,st,20);
	now->ost=ost;
	total++;
}

static char isdest(const char *st)
{
	return (st[SaXYL(3,1)]=='A' && st[SaXYL(4,1)]=='B'
	      &&st[SaXYL(3,2)]=='C' && st[SaXYL(4,2)]=='D');
}

static void trymoves(struct st *sts)
{
char *st=sts->data;
stt nst;
int blk[2],bli,oi,nbp;
static const char offs[4][2]={{0,-1},{+1,0},{0,+1},{-1,0}};
char bx,by,nbx,nby,gx=0,gy=0,gxs=0,gys=0,sx,sy,xi,yi;

#if 0
/*ndef NDEBUG*/
	printf("Entered trymoves()\n");
	dumpst(st);
#endif
	if (isdest(st)) {
struct st *o;
int lev=0;
struct back {
	struct back *next;
	struct st *st;
	} *back=NULL,*b;
		for (o=sts;o;o=o->ost) {
			chk(b=alloca(sizeof(*b)));
			b->next=back;
			back=b;
			b->st=o;
			}

		solutions++;
#ifndef BENCHMARK
#if 1
		puts("*** GOAL");
#else
		printf("*** GOAL: level=%d\n",level);
#endif
#endif
		while (back) {
#ifndef BENCHMARK
			printf("> /-------\\ forwardtrace: level=%d\n",lev++);
			dumpst(back->st->data);
#endif
			back=back->next;
			}
		}
	blk[0]=((char *)memchr(st           ,'+',20           ))-((char *)st); assert(blk[0]<20);
	blk[1]=((char *)memchr(st+(blk[0]+1),'+',20-(blk[0]+1)))-((char *)st); assert(blk[1]<20);
	assert(!memchr(st+(blk[1]+1),'+',20-(blk[1]+1)));
	for (bli=0;bli<2;bli++) {
		SaLXY(blk[bli],bx,by);
		for (oi=0;oi<4;oi++) {
			nbx=bx+(sx=offs[oi][0]);
			nby=by+(sy=offs[oi][1]);
			if (nbx<0 || nbx>=5 || nby<0 || nby>=4) {
failed: continue;
				}

#define CHKPOS(xs,ys,dx,dy) do { char nxb=nbx-dx,nyb=nby-dy; \
	if (nxb<0 || nxb+xs>5 || nyb<0 || nyb+ys>5) goto failed; \
	for (xi=0;xi<(xs);xi++) for (yi=0;yi<(ys);yi++) { \
		if (xi-sx>=0&&xi-sx<xs&&yi-sy>=0&&yi-sy<ys) continue; \
		if (st[SaXYL(bx-dx+xi,by-dy+yi) ]!='+') goto failed; \
		} \
  gx=nbx-dx; gy=nby-dy; gxs=xs; gys=ys; \
  } while (0)

			nbp=SaXYL(nbx,nby);
			switch (st[nbp]) {
				case '{': CHKPOS(2,1, 0, 0); break;
				case '}': CHKPOS(2,1,+1, 0); break;
				case '^': CHKPOS(1,2, 0, 0); break;
				case 'v': CHKPOS(1,2, 0,+1); break;
				case '#': CHKPOS(1,1, 0, 0); break;
				case 'A': CHKPOS(2,2, 0, 0); break;
				case 'B': CHKPOS(2,2,+1, 0); break;
				case 'C': CHKPOS(2,2, 0,+1); break;
				case 'D': CHKPOS(2,2,+1,+1); break;
				case '+': goto failed;
				default:  assert(0);
				}
#undef CHKPOS

			memcpy(nst,st,20);
			for (yi=gy;yi<gy+gys;yi++) memset(nst+SaXYL(gx,yi),'+',gxs);
			for (yi=gy;yi<gy+gys;yi++) memcpy(nst+SaXYL(gx-sx,yi-sy),st+SaXYL(gx,yi),gxs);
#if 0
/*ndef NDEBUG*/
			printf("Moving: g=(%d,%d)[%d,%d] by (%d,%d)\n",gx,gy,gxs,gys,-sx,-sy);
			dumpst(nst);
#endif
			addstate(nst,sts);
			}
		}
}

static void swtogo(void)
{
	assert(!togonow);
	togonow=togo;
	togo=NULL;
	togop=&togo;
	level++;
}

int main(void)
{
struct st *now;
#ifdef STSTEP
unsigned ststep=0;
#endif

	addstate(init,NULL);
	while (togo) {
		swtogo();
		while ((now=togonow)) {
			togonow=now->nexttogo;
			trymoves(now);
#ifdef STSTEP
			gone++;
#if 1
			if (!(gone%STSTEP)) printf("%5u+%5u=%5u\n",gone,total-gone,total);
#else
			if (++ststep==STSTEP || !togo) {
				printf("%5u+%5u=%5u, level=%3d\n",gone,total-gone,total,level);
				ststep=0;
				}
#endif
#endif
			}
		}
#if 0
	printf("total=%u, maxlevel=%d, solutions=%d\n",total,level,solutions);
#endif
	return(EXIT_SUCCESS);
}