题目：The Rotation Game
思路：bfs三次。目前还是TLE，好像是判重出了问题，下次再来写。
贴个代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<sstream>
#include<queue>
using namespace std;#define k 3
#define num 8
#define n 7
#define m 24
#define modMAX 1000007struct Pair {int x,y;Pair() {}Pair(int xx,int yy) {x=xx,y=yy;}
};Pair a[k+1][num+1];
bool Hash[modMAX]= {0};
string Min;struct State {string Move;bool x[n+1][n+1];int Mark;State() {Move="";memset(x,0,sizeof(x));}State(State old,int m1,int m2,char add,int dir) {memcpy(x,old.x,sizeof(x));Move=old.Move+add;if(dir==-1&&m1==-1) {int t=x[1][m2];for(int i=2; i<=n; i++) {x[i-1][m2]=x[i][m2];}x[n][m2]=t;}if(dir==1&&m1==-1) {int t=x[n][m2];for(int i=n; i>=2; i--) {x[i][m2]=x[i-1][m2];}x[1][m2]=t;}if(dir==1&&m2==-1) {int t=x[m1][n];for(int i=n; i>=2; i--) {x[m1][i]=x[m1][i-1];}x[m1][1]=t;}if(dir==-1&&m2==-1) {int t=x[m1][1];for(int i=2; i<=n; i++) {x[m1][i-1]=x[m1][i];}x[m1][n]=t;}}void make_mark() {int in1[m+1]= {0,1,1,2,2,3,3,3,3,3,3,3,4,4,5,5,5,5,5,5,5,6,6,7,7};int in2[m+1]= {0,3,5,3,5,1,2,3,4,5,6,7,3,5,1,2,3,4,5,6,7,3,5,3,5};Mark=0;for(int i=1; i<=m; i++) {Mark=Mark*2+x[in1[i]][in2[i]];Mark%=modMAX;}}bool judge() {int M1[num+1]= {0,3,3,3,4,4,5,5,5};int M2[num+1]= {0,3,4,5,3,5,3,4,5};for(int i=1; i<=num; i++) {if(!x[M1[i]][M2[i]]) return false;}return true;}void print() {for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {cout<<x[i][j]<<' ';}cout<<endl;}}
};State make(int x) {State y;for(int i=1; i<=num; i++) {y.x[a[x][i].x][a[x][i].y]=true;}y.make_mark();return y;
}bool init() {memset(a,0,sizeof(a));int in1[m+1]= {0,1,1,2,2,3,3,3,3,3,3,3,4,4,5,5,5,5,5,5,5,6,6,7,7};int in2[m+1]= {0,3,5,3,5,1,2,3,4,5,6,7,3,5,1,2,3,4,5,6,7,3,5,3,5};int x;scanf("%d",&x);if(!x) return false;int c[k+1]= {0};a[x][++c[x]]=Pair(in1[1],in2[1]);for(int i=2; i<=m; i++) {scanf("%d",&x);a[x][++c[x]]=Pair(in1[i],in2[i]);}return true;
}State bfs(State in) {memset(Hash,0,sizeof(Hash));int M1[num+1] = {0,-1,-1, 3, 5,-1,-1, 5, 3};int M2[num+1] = {0, 3, 5,-1,-1, 5, 3,-1,-1};int dir[num+1]= {0,-1,-1, 1, 1, 1, 1,-1,-1};queue<State> que;que.push(in);Hash[in.Mark]=true;while(!que.empty()) {State head=que.front();que.pop();if(head.Move.size()>=Min.size()){head.Move+="z";return head;}for(int i=1; i<=num; i++) {State x=State(head,M1[i],M2[i],i+'A'-1,dir[i]);x.make_mark();if(x.judge()) return x;if(!Hash[x.Mark]) {Hash[x.Mark]=true;que.push(x);}}}return State();
}int main() {while(init()) {int flag=0;for(int i=1; i<=64; i++) Min+='Z';int what;for(int i=1; i<=k; i++) {flag=i;State in=make(i);if(in.judge()) goto END;State x=bfs(in);if(x.Move.size()<Min.size()||(x.Move.size()==Min.size()&&x.Move<Min)) {Min=x.Move;what=i;}}cout<<Min<<endl<<what<<endl;continue;
END: printf("No moves needed\n%d\n",flag);}return 0;
}