> #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];
> int maxDFS(int k,int step)
> {
> 	return 0;
> }
> int dfs(int k,int dep)
> {
> 	if(b[k]!=-1)
> 		return b[k];
> 	if(v[k]!=dep)
> 		return 0;	
> 	int i,d=0;
> 	--dep;
> 	for(i=0;i<16;++i)
> 		if(k&BIN(i))
> 		{
> 			if(i-4>=0 && !KB(i-4))
> 				d += dfs((k|BIN(i-4))&(~BIN(i)),dep);
> 			if(i+4<16 && !KB(i+4))
> 				d += dfs((k|BIN(i+4))&(~BIN(i)),dep);
> 			if(i%4 != 0 && !KB(i-1))
> 				d += dfs((k|BIN(i-1))&(~BIN(i)),dep);
> 			if(i%4!=3 && !KB(i+1))
> 				d += dfs((k|BIN(i+1))&(~BIN(i)),dep);
> 		}
> 	return b[k] = d;
> }
> 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);
> 	for(i=0;i<9;++i)
> 		v[a[i]]=0,s[i]=a[i];
> 	for(r=0,f=9;v[d]==inf;++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;
> 					}
> 				}
> 				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;
> 					}
> 				}
> 				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;
> 					}
> 				}
> 				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;
> 					}
> 				}
> 			}
> 	}
> 	if(min < v[d])
> 		return ;
> 	std::fill(b,b+(1<<16),-1);
> 	for(i=0;i<9;++i)
> 		b[a[i]] = 1;
> 	k = dfs(d,v[d]);
> 	if(min == v[d])
> 		sum += k;
> 	else
> 	{
> 		min = v[d];
> 		sum = k;
> 	}
> }
> 
> 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;
> 	}
> }

• 查查越界之类的问题吧，说不定是那个 (0) frkstyc 2005-07-31 23:12:42
  • Re:不会是越界吧，而且我也想不出哪儿可能，再说是TLE (0) lookus 2005-07-31 23:20:03
    • 假如你局部越界覆盖了栈里面的东西的话，要TLE也不是很难 (0) frkstyc 2005-07-31 23:22:34
      • Re:我刚才把数组开大了一倍，还是TLE，是不是这个算法不行啊 (0) lookus 2005-07-31 23:30:50
        • Re:刚才试了一下，只那个BFS就超了，ft (0) lookus 2005-07-31 23:32:51
          • 你有没有判重啊 (0) frkstyc 2005-07-31 23:33:53