其实这题可以直接二进制状压做，1表示黑棋，0表示白棋，另外记录下2个空点的位置就行了。
具体看代码（冗长）：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;++i)
#define dop(i,m,n) for(int i=m;i>=n;--i)
#define lowbit(x) (x&(-x))
#define ll long long
#define INF 2147483647
#define re register
#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
#define Close fclose(stdin);fclose(stdout);
#define pause system("pause");
using namespace std;
inline int read(){
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
char a[6][6];
struct Node{
int x[2], y[2], s, time, who; //x,y数组记录2个空点的位置，s表示当前的状态（二进制），who表示到谁走了
}start, begin, now, tmp;
int getHash(){ //棋盘转二进制状态
int ans = 0;
rep(i, 1, 4) rep(j, 1, 4) if(a[i][j] == 'B') ans |= (1 << ( ((i - 1) << 2) + j - 1) );
return ans;
}
queue <Node> q;
bool Win(Node x){ //判赢函数
int s = x.s;
//判断有没有黑点四子连棋
if( s&1&&s&(1<<4)&&s&(1<<8)&&s&(1<<12) || s&(1<<1)&&s&(1<<5)&&s&(1<<9)&&s&(1<<13)
|| s&(1<<2)&&s&(1<<6)&&s&(1<<10)&&s&(1<<14) || s&(1<<3)&&s&(1<<7)&&s&(1<<11)&&s&(1<<15)
|| s&1&&s&(1<<1)&&s&(1<<2)&&s&(1<<3) || s&(1<<4)&&s&(1<<5)&&s&(1<<6)&&s&(1<<7)
|| s&(1<<8)&&s&(1<<9)&&s&(1<<10)&&s&(1<<11) || s&(1<<12)&&s&(1<<13)&&s&(1<<14)&&s&(1<<15)
|| s&1&&s&(1<<5)&&s&(1<<10)&&s&(1<<15) || s&(1<<3)&&s&(1<<6)&&s&(1<<9)&&s&(1<<12))
return true;
//把空点的位置赋值为1
s|=1<<(((x.x[0]-1)<<2)+x.y[0]-1); s|=1<<(((x.x[1]-1)<<2)+x.y[1]-1);
//rep(i, 1, 4){ rep(j, 1, 4) printf("%d ", (s>>(((i-1)<<2)+j-1))&1); printf("\n"); }
//判断白点有没有四子连棋
if( (s^1)&1&&(s^(1<<4))&(1<<4)&&(s^(1<<8))&(1<<8)&&(s^(1<<12))&(1<<12) || (s^(1<<1))&(1<<1)&&(s^(1<<5))&(1<<5)&&(s^(1<<9))&(1<<9)&&(s^(1<<13))&(1<<13)
|| (s^(1<<2))&(1<<2)&&(s^(1<<6))&(1<<6)&&(s^(1<<10))&(1<<10)&&(s^(1<<14))&(1<<14) || (s^(1<<3))&(1<<3)&&(s^(1<<7))&(1<<7)&&(s^(1<<11))&(1<<11)&&(s^(1<<15))&(1<<15)
|| (s^1)&&(s^(1<<1))&(1<<1)&&(s^(1<<2))&(1<<2)&&(s^(1<<3))&(1<<3) || (s^(1<<4))&(1<<4)&&(s^(1<<5))&(1<<5)&&(s^(1<<6))&(1<<6)&&(s^(1<<7))&(1<<7)
|| (s^(1<<8))&(1<<8)&&(s^(1<<9))&(1<<9)&&(s^(1<<10))&(1<<10)&&(s^(1<<11))&(1<<11) || (s^(1<<12))&(1<<12)&&(s^(1<<13))&(1<<13)&&(s^(1<<14))&(1<<14)&&(s^(1<<15))&(1<<15)
|| (s^1)&(1)&&(s^(1<<5))&(1<<5)&&(s^(1<<10))&(1<<10)&&(s^(1<<15))&(1<<15) || (s^(1<<3))&(1<<3)&&(s^(1<<6))&(1<<6)&&(s^(1<<9))&(1<<9)&&(s^(1<<12))&(1<<12))
return true;
return false;
}
int l[] = { 233, -1, 1, 0, 0 }, r[] = { 666, 0, 0, -1, 1 }, id, X, Y, kong, v[20000010];
int getHash(Node x){ //不要hack我
return x.s + x.x[0] * 10007 + x.x[1] * 107 + x.y[1] * 677 + x.y[0] * 97;
}
int main(){
rep(i, 1, 4)
rep(j, 1, 4){
cin>>a[i][j];
if(a[i][j] == 'O') //记录空点位置
if(!start.x[0]) start.x[0] = i, start.y[0] = j;
else start.x[1] = i, start.y[1] = j;
}
start.s = getHash();
start.time = 0;
begin = start;
start.who = 0;
begin.who = 1;
q.push(start);
q.push(begin);
v[getHash(begin)] = v[getHash(start)] = 1;
while(!q.empty()){ //bfs
Node now = q.front();
q.pop();
rep(i, 0, 1){
rep(j, 1, 4){
X = now.x[i] + l[j]; Y = now.y[i] + r[j];
if(X <= 0 || X > 4 || Y <= 0 || Y > 4 || X == now.x[i^1] && Y == now.y[i^1]) continue; //不能出界，也不能走到另外一个空点
id = ((X - 1) << 2) + Y - 1;
kong = ((now.x[i] - 1) << 2) + now.y[i] - 1;
if(((now.s >> id) & 1) == now.who){ //如果是到这个棋走
tmp = now;
tmp.s &= ~(1 << id); //交换
tmp.s |= tmp.who << kong; //位置
tmp.x[i] = X;
tmp.y[i] = Y;
if(v[getHash(tmp)]) continue;
v[getHash(tmp)] = 1;
tmp.time++;
tmp.who^=1;
if(Win(tmp)){
printf("%d\n", tmp.time);
return 0;
}
q.push(tmp);
}
}
}
}
return 0;
}