USACO 3.2.5 – Magic Squares

#include <cstdio>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int main() {
	freopen("msquare.in", "r", stdin), freopen("msquare.out", "w", stdout);
	string f="        ", s="12345678",seq,st,en,rev;
	char c; map<string, int> v;

	for(int i=0;i<8;i++,getchar()) f[i]= getchar();

	queue<string> q; q.push(s), q.push("");
	while(q.size()){
		s=q.front(), q.pop(), seq = q.front(), q.pop();
		if(v[s]++) continue;
		if(s==f){
			printf("%d\n%s\n", seq.size(), seq.c_str());
			return 0;
		}
		rev=string(s.rbegin(), s.rend());
		q.push(rev), q.push(seq+'A');

		st=s.substr(0,4),en=s.substr(4,4);
		rotate(st.begin(), st.begin()+3, st.end()),rotate(en.begin(),en.begin()+1,en.end());
		q.push(st+en), q.push(seq+'B');

		c =s[1],s[1]=s[6],s[6]=s[5],s[5]=s[2],s[2]=c;
		q.push(s), q.push(seq+'C');
	}
	puts("NONE");
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: