方法是建立dfs，并在其中加入pre变量，记录之前移动的是W还是B。外面套for循环，从1步开始逐次递增，直到在i步时可以走完（dfs返回1），break退出循环，即为最短步。
本题的关键主要是可能有走过来又走回去的无用情况。对于这道题，即使在最坏的情况，也基本上可以保证在15步以内（并未证明）达到目标状态，所以可以在dfs中加入step进行限制，step等于外面for循环中的循环变量时就结束。这样就有效避免了死循环的出现，对于处理这道题的情况比较方便。
注：以下代码未考虑起始时就满足条件的情况。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char a[][];
int dir[][]={{,},{,-},{,},{-,}},ans,ox1=-,ox2,oy1,oy2;//dir数组储存方向，ox\oy记录两个空位
bool check()//检验此时棋盘是否满足条件
{
if(a[][]==a[][]&&a[][]==a[][]&&a[][]==a[][])
return true;
if(a[][]==a[][]&&a[][]==a[][]&&a[][]==a[][])
return ;
for(int i=;i<;i++)
{
if(a[i][]==a[i][]&&a[i][]==a[i][]&&a[i][]==a[i][])
return ;
if(a[][i]==a[][i]&&a[][i]==a[][i]&&a[][i]==a[][i])
return ;
}
return ;
}
bool val(int x,int y,char p)//检验位置是否合法
{
return x>=&&x<&&y>=&&y<&&a[x][y]!=p;
}
bool dfs(int x1,int y1,int x2,int y2,char pre,int step)
{
if(step==ans)
{
if(check()) return ;
else return false;
}
for(int i=;i<;i++)
{
int xn,yn,xm,ym;
xn=x1+dir[i][];
xm=x2+dir[i][];
yn=y1+dir[i][];
ym=y2+dir[i][];
if(val(xn,yn,pre))
{
swap(a[x1][y1],a[xn][yn]);
if(dfs(xn,yn,x2,y2,(pre=='B'?'W':'B'),step+))return ;//灵活运用三元运算符
swap(a[x1][y1],a[xn][yn]);
}
if(val(xm,ym,pre))
{
swap(a[x2][y2],a[xm][ym]);
if(dfs(x1,y1,xm,ym,(pre=='B'?'W':'B'),step+))return ;
swap(a[x2][y2],a[xm][ym]);
}
}
return ;
}
int main()
{
int i,x=,j;
for(i=;i<;i++)
scanf("%s",a[i]);
for(i=;i<;i++)
{
for(j=;j<;j++)
{
if(a[i][j]=='O')
{
if(ox1==-)
{
ox1=i;oy1=j;
}
else
{ox2=i;oy2=j;}
}
}
}
for(ans=;ans<;ans++)//从第一步开始逐次进行
{
if(dfs(ox1,oy1,ox2,oy2,'W',))
break;
if(dfs(ox1,oy1,ox2,oy2,'B',))
break;
}
printf("%d\n",ans);
return ;
}