题目大意：给定一个大小为 4*4 的棋盘，分别有 7 个黑子、7 个白子和 2 个空位构成，求出至少需要移动多少步，才能使得四个相同的棋子共线。

题解：显然每一种棋盘的局面都是一个状态，因此需要采用状态压缩的搜索。总共的局面最多有4e7种，并且所给的内存足够开下哈希表。

需要注意的是，数据中有很多不是对称的情况，因此需要分别考虑先移动白子和黑子的情况，再取最小值，得到答案。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=5e7;

const int inf=0x3f3f3f3f;

const int dx[]={0,0,-1,1};

const int dy[]={1,-1,0,0};

//b->1 w->0 o->2

char s[10];

int state[5][5],mp[2][maxn],ans=inf,st;

bool col[maxn]; //b->1 w->0

int get_hash(int a[5][5]){

	int val=0;

	for(int i=1;i<=4;i++)

		for(int j=1;j<=4;j++)

			val=val*3+a[i][j];

	return val;

}

void get_state(int val){

	for(int i=1;i<=4;i++)

		for(int j=1;j<=4;j++)

			state[i][j]=val%3,val/=3;

}

void read_and_parse(){

	for(int i=1;i<=4;i++){

		scanf("%s",s+1);

		for(int j=1;j<=4;j++){

			if(s[j]=='B')state[i][j]=1;

			if(s[j]=='W')state[i][j]=0;

			if(s[j]=='O')state[i][j]=2;

		}

	}

	st=get_hash(state);

}

bool right(int x,int y,int cor){

	if(x<1||y<1||x>4||y>4||state[x][y]!=cor)return 0;

	return 1;

}

bool check(int a[5][5]){

	for(int i=1;i<=4;i++){

		if(a[i][1]==a[i][2]&&a[i][2]==a[i][3]&&a[i][3]==a[i][4])return 1;

		if(a[1][i]==a[2][i]&&a[2][i]==a[3][i]&&a[3][i]==a[4][i])return 1;

	}

	if(a[1][1]==a[2][2]&&a[2][2]==a[3][3]&&a[3][3]==a[4][4])return 1;

	if(a[1][4]==a[2][3]&&a[2][3]==a[3][2]&&a[3][2]==a[4][1])return 1;

	return 0;

}

void solve(int cor){

	queue<int> q;

	q.push(st),mp[cor][st]=1,col[st]=cor;

	while(q.size()){

		int u=q.front();q.pop();

		get_state(u);

		if(check(state)){ans=min(ans,mp[cor][u]-1);return;}

		for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)if(state[i][j]==2){

			for(int k=0;k<4;k++){

				int nx=i+dx[k],ny=j+dy[k];

				if(!right(nx,ny,col[u]))continue;

				swap(state[i][j],state[nx][ny]);

				int v=get_hash(state);

				if(!mp[cor][v])mp[cor][v]=mp[cor][u]+1,col[v]=col[u]^1,q.push(v);

				swap(state[i][j],state[nx][ny]);

			}

		}

	}

}

int main(){

	read_and_parse();

	solve(1);solve(0);

	printf("%d\n",ans);

	return 0;

}