#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
struct node
{
int a[5][5];
int space_x[5],space_y[5];
int step;
int who;
};
queue<node> q;
bool check(node x)
{
for(int i=1;i<=4;i++)
{
if(x.a[i][1] == 0 && x.a[i][2] == 0 && x.a[i][3] == 0 && x.a[i][4] == 0) return true;
if(x.a[i][1] == 1 && x.a[i][2] == 1 && x.a[i][3] == 1 && x.a[i][4] == 1) return true;
if(x.a[1][i] == 0 && x.a[2][i] == 0 && x.a[3][i] == 0 && x.a[4][i] == 0) return true;
if(x.a[1][i] == 1 && x.a[2][i] == 1 && x.a[3][i] == 1 && x.a[4][i] == 1) return true;
}
if(x.a[1][1] == 0 && x.a[2][2] == 0 && x.a[3][3] == 0 && x.a[4][4] == 0) return true;
if(x.a[1][1] == 1 && x.a[2][2] == 1 && x.a[3][3] == 1 && x.a[4][4] == 1) return true;
if(x.a[1][4] == 0 && x.a[2][3] == 0 && x.a[3][2] == 0 && x.a[4][1] == 0) return true;
if(x.a[1][4] == 1 && x.a[2][3] == 1 && x.a[3][2] == 1 && x.a[4][1] == 1) return true;
return false;
}
void place_swap(int &a,int &b)
{
a ^= b;
b ^= a;
a ^= b;
return ;
}
int bfs()
{
while(!q.empty())
{
node now = q.front();
q.pop();
if(check(now)) return now.step;
for(int o=1;o<=2;o++)
{
int x = now.space_x[o],y = now.space_y[o];
for(int i=0;i<4;i++)
{
int xnew = x + dx[i],ynew = y + dy[i];
if(xnew < 1 || xnew > 4 || ynew < 1 || ynew > 4 || now.a[xnew][ynew] == 2 || now.a[xnew][ynew] == now.who) continue;
node next = now;
place_swap(next.a[x][y],next.a[xnew][ynew]);
next.space_x[o] = xnew;
next.space_y[o] = ynew;
next.who ^= 1;
next.step++;
q.push(next);
}
}
}
return -1;
}
int main()
{
node start;
bool flag = false;
start.step = 0;
for(int i=1;i<=4;i++)
{
string s;
cin >> s;
s = " " + s;
for(int j=1;j<=4;j++)
{
if(s[j] == 'B') start.a[i][j] = 1;
if(s[j] == 'W') start.a[i][j] = 0;
if(s[j] == 'O')
{
start.a[i][j] = 2;
if(flag == false)
{
start.space_x[1] = i;
start.space_y[1] = j;
}
else
{
start.space_x[2] = i;
start.space_y[2] = j;
}
}
}
}
start.who = 0;
q.push(start);
start.who = 1;
q.push(start);
int ans = bfs();
printf("%d",ans);
return 0;
}
WA on #1,#2,#5。