#include <iostream.h>
#include <string.h>
#include <algorithm>
#define inf 20000000
#define KB(i) (k&(1<<(i)))
#define BIN(i) (1<<(i))
int b[1<<16],v[1<<16],s[1<<16],min,sum;
int a[]={51,102,204,816,1632,3264,13056,26112,52224};
char str[20];
void minBFS(char c)
{
	int k=0,r,f,i,j,d;
	for(i=0;i<16;++i)
		if(str[i]==c)
			k |= BIN(i);
	d = k;
	std::fill(v,v+(1<<16),inf);
	memset(b,0,sizeof(b));
	for(i=0;i<9;++i)
		v[a[i]]=0,s[i]=a[i],b[a[i]]=1;
	for(r=0,f=9;v[d]==inf || v[s[r]]<r;++r)
	{
		k = s[r];
		for(i=0;i<16;++i)
			if(k&BIN(i))
			{
				if(i-4>=0 && !KB(i-4))
				{
					j = ((k|BIN(i-4))&(~BIN(i)));
					if(v[j]==inf)
					{
						v[j] = v[k]+1;
						s[f++] = j;
						b[j]=b[k];
					}
					else
						if(v[j]==v[k]+1)
							b[j]+=b[k];
				}
				if(i+4<16 && !KB(i+4))
				{
					j = ((k|BIN(i+4))&(~BIN(i)));
					if(v[j]==inf)
					{
						v[j] = v[k]+1;
						s[f++] = j;
						b[j]=b[k];
					}
					else
						if(v[j]==v[k]+1)
							b[j]+=b[k];
				}
				if(i%4 != 0 && !KB(i-1))
				{
					j = ((k|BIN(i-1))&(~BIN(i)));
					if(v[j]==inf)
					{
						v[j] = v[k]+1;
						s[f++] = j;
						b[j]=b[k];
					}
					else
						if(v[j]==v[k]+1)
							b[j]+=b[k];
				}
				if(i%4!=3 && !KB(i+1))
				{
					j = ((k|BIN(i+1))&(~BIN(i)));
					if(v[j]==inf)
					{
						v[j] = v[k]+1;
						s[f++] = j;
						b[j]=b[k];
					}
					else
						if(v[j]==v[k]+1)
							b[j]+=b[k];
				}
			}
	}
	if(min < v[d])
		return ;
	if(min == v[d])
		sum += b[d];
	else
	{
		min = v[d];
		sum = b[d];
	}
}
void minStep()
{
	min = inf;
	minBFS('A');
	minBFS('B');
	minBFS('C');
	minBFS('D');
}
void main()
{
	char st[4];
	int i;
	while(cin>>str)
	{
		for(i=0;i<3;++i)
		{
			cin>>st;
			strcat(str,st);
		}
		minStep();
		cout<<min<<" "<<sum<<endl;
	}
}

• 一次过全部算好，然后查表…… (2102) frkstyc 2005-08-01 03:26:34