mobian.cpp

【USACO3.2.5】魔板

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

struct node
{
	char op;
	int front;
	int num[8];
};

char flag[40321];
int index[40321];
int step[40321];
node quene[40321];
int head[8] = {1 , 2, 3 , 4, 8, 7, 6, 5};
int numtemp[7] = {5040,720,120,24,6,2,1};
int getnum[3][8] = {4 ,5 ,6 ,7 ,0 ,1 ,2 ,3, 3 ,0 ,1 ,2 ,7 ,4 ,5 ,6, 0 ,5 ,1 ,3 ,4 ,6 ,2 ,7 };


int getpos(int *p)
{
	int n,m,num;
	int count[8];
	for(n = 0 ; n < 8; n++) count[n] = n;
	for(n = 0 , num = 0; n < 7; n++)
	{
		num = num + (count[p[n]-1]) * numtemp[n];
		for(m = p[n]-1;m < 8;m++) count[m]--;
	}
	return num;
}

void getpath(int p)
{
	if(quene[p].op == '*')
		return;
	getpath(quene[p].front);
	printf("%c",quene[p].op);
}

void initBFS()
{
	int tp[8];
	node ntp;
	int count;
	int len,pos;
	int i,j,k,h;

	memset(flag,0,sizeof(char)*40321);
	len = 1;
	quene[0].op = '*';
	quene[0].front = -1;
	memcpy(quene[0].num,head,sizeof(int)*8);
	pos = getpos(quene[0].num);
	step[pos] = 0;
	flag[pos] = 1;
	
	count = 1;
	for(i = 0;i<len;count++)
	{
		h = len;
		for(;i<h;i++)
		{

			ntp = quene[i];

			for(j=0;j<3;j++)
			{
				for(k=0;k<8;k++)
				{
					quene[len].num[k] = ntp.num[getnum[j][k]];			
				}


				pos = getpos(quene[len].num);

				if(flag[pos] == 0)
				{
					flag[pos] = 1;
					index[pos] = len;
					quene[len].front = i;
					quene[len].op = j + 'A';
					step[pos] = count;
					len = len + 1;
				}
			}
		}
	}
}

int main()
{
	int i,j,p,num[8];
	initBFS();
	i = 0;
	while(scanf("%d",&num[i++])!=EOF)
	{
		if(i == 8)
		{
			j = num[7]; num[7] = num[4]; num[4] = j;
			j = num[6]; num[6] = num[5]; num[5] = j;
			p = getpos(num);
			printf("%d\n",step[p]);
			getpath(index[p]);
			printf("\n");
			i = 0;
		}
	}

	return 0;
}