USACO3.2 Magic Squares(square)

BFS+多次元配列判定、状態数8!出力は実は60文字の1行を判断する必要はありません.BFSは22階まで40316程度の状況があり、すべての40320に近いからです.だからいくら強いデータでも60歩には届かない.プログラムが似ているので,この問題はあまり上手ではない.
 

/*
ID:jzzlee1
PROB:msquare
LANG:C++
*/
//#include<iostream>
#include<fstream>
#include<cstring>
#include<queue>
#include<string>
using namespace std;
ifstream cin("msquare.in");
ofstream cout("msquare.out");
short r[3][5];  //    
short a[3][5];  //    
short tmp;
bool  vis[9][9][9][9][9][9][9]; //  
struct  node     //         
{
	int dep;     //          
	string str;  //       
	short b[3][5];//     
}q[50000];        //BFS         40320   ,          
int head,tail;
void input()
{
	for(int j=1; j<=4; j++)
		cin>>r[1][j];
	for(int i=4; i>=1; i--)
		cin>>r[2][i];
	for(int i=1; i<=4; i++)
	{
		a[1][i] = i;
		a[2][i] = 8-i+1;
	}
}
inline void A(short (*b)[5])    //  A
{
	for(int i=1; i<=4; i++)
	{
		tmp = b[1][i];
		b[1][i] = b[2][i];
		b[2][i] = tmp;
	}
}
inline void B(short (*b)[5])
{
	b[1][0] = b[1][4];
	b[2][0] = b[2][4];
	for(int i=4; i>=1; i--)
	{
		b[1][i] = b[1][i-1];
		b[2][i] = b[2][i-1];
	}
}
inline void C(short (*b)[5])
{
	tmp = b[1][3];
	b[1][3] = b[1][2];
	b[1][2] = b[2][2];
	b[2][2] = b[2][3];
	b[2][3] = tmp;
}
inline bool isequal(short (*r)[5],short (*b)[5])
{
	for(int i=1; i<=2; i++)
		for(int j=1; j<=4; j++)
			if(r[i][j]!=b[i][j])
				return false;
	return true;
}
void BFS()
{
	memset(vis,0,sizeof(vis));
	//       
	memcpy(q[0].b,a,sizeof(a));
	q[0].dep=0;
	q[0].str = "";
	head = 0;
	tail = 1;
	vis[q[0].b[1][1]][q[0].b[1][2]][q[0].b[1][3]][q[0].b[1][4]][q[0].b[2][1]][q[0].b[2][2]][q[0].b[2][3]] = 1;
	node next;
	node p;
	while(1)
	{
		p = q[head];
		head++;
		head%=50000;
		if(isequal(r,p.b))
		{
			cout<<p.dep<<endl;
			cout<<p.str<<endl;
			break;
		}
		//A
		next = p;
		next.dep = p.dep+1;
		next.str = p.str+"A"; 
		A(next.b);
		if(!vis[next.b[1][1]][next.b[1][2]][next.b[1][3]][next.b[1][4]][next.b[2][1]][next.b[2][2]][next.b[2][3]])
		{
			q[tail] = next;
			tail++;
			tail%=50000;
			vis[next.b[1][1]][next.b[1][2]][next.b[1][3]][next.b[1][4]][next.b[2][1]][next.b[2][2]][next.b[2][3]] = 1;
		}
		//B
		next = p;
		next.dep = p.dep+1;
		next.str = p.str+"B"; 
		B(next.b);
		if(!vis[next.b[1][1]][next.b[1][2]][next.b[1][3]][next.b[1][4]][next.b[2][1]][next.b[2][2]][next.b[2][3]])
		{
			q[tail] = next;
			tail++;
			tail%=50000;
			vis[next.b[1][1]][next.b[1][2]][next.b[1][3]][next.b[1][4]][next.b[2][1]][next.b[2][2]][next.b[2][3]] = 1;
		}
		//C
		next = p;
		next.dep = p.dep+1;
		next.str = p.str+"C";
		C(next.b);
		if(!vis[next.b[1][1]][next.b[1][2]][next.b[1][3]][next.b[1][4]][next.b[2][1]][next.b[2][2]][next.b[2][3]])
		{
			q[tail] = next;
			tail++;
			tail%=50000;
			vis[next.b[1][1]][next.b[1][2]][next.b[1][3]][next.b[1][4]][next.b[2][1]][next.b[2][2]][next.b[2][3]] = 1;
		}
	}
}
int main()
{
	input();
	BFS();
	return 0;
}