WA on #5

（ @roumeideclown 被禁言了，帮他发一下）

#include<bits/stdc++.h>
#pragma G++ optimize(2)
//#pragma G++ optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
struct node {
	char a[5][5],col;
	int step;
};
map<string,int> vis;
queue<node> q;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
string calc(node st) {
	string res="";
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			res=res+st.a[i][j];
	return st.col+"$"+res;
}
bool check(node u) {
	for(int i=1;i<=4;i++) {
		if(u.a[i][1]==u.a[i][2]&&u.a[i][1]==u.a[i][3]&&u.a[i][1]==u.a[i][4]) return 1;
		if(u.a[1][i]==u.a[2][i]&&u.a[1][i]==u.a[3][i]&&u.a[1][i]==u.a[4][i]) return 1;
	}
	if(u.a[1][1]==u.a[2][2]&&u.a[1][1]==u.a[3][3]&&u.a[1][1]==u.a[4][4]) return 1;
	if(u.a[1][4]==u.a[2][3]&&u.a[1][4]==u.a[3][2]&&u.a[1][4]==u.a[4][1]) return 1;
	return 0;
}
int bfs(node st) {
	st.col='B';
	vis[calc(st)]=1;
	st.col='W';
	vis[calc(st)]=1;
	q.push(st);
	while(!q.empty()) {
		node u=q.front();
		q.pop();
		if(check(u)) return u.step;
		for(int i=1;i<=4;i++) {
			for(int j=1;j<=4;j++) {
				if(u.a[i][j]=='O') {
					for(int k=0;k<4;k++) {
						int nx=i+dx[k],ny=j+dy[k];
						if(nx<1||nx>4||ny<1||ny>4) continue;
						if(u.a[nx][ny]==u.col) {
							node v;
							for(int i1=1;i1<=4;i1++) 
								for(int j1=1;j1<=4;j1++) 
									v.a[i1][j1]=u.a[i1][j1];
							swap(v.a[nx][ny],v.a[i][j]);
							v.col=(u.col=='B'?'W':'B');
							v.step=u.step+1;
							if(!vis.count(calc(v))) {
								vis[calc(v)]=1;
								q.push(v);
							}
						}
					}
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	node st;
	for(int i=1;i<=4;i++) 
		for(int j=1;j<=4;j++) 
			cin>>st.a[i][j];
	cout<<bfs(st);
	return 0;
}