原题链接

迭代加深。

枚举多少步能到达目标棋局，然后搜索判断。

第一次从白色开始走，第二次从黑色开始走，或者反过来。实际搜索的时候，当前操作需要和上从不一样，所以我们定义 dfs(int k,int px1,int py1,int px2,int py2,int c) 表示当前移动次数，两个空白位置的坐标和上一次移动的颜色，最后到达步数判断一下是否到达目标棋局即可。

值得注意的是，存在不移动就可到达目标棋局的情况，需要特判。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=10;
char ch[N][N];
int dx1,dy1,dx2,dy2,a[N][N],cnt,fx[N]={0,0,1,0,-1},fy[N]={0,1,0,-1,0};
bool check()//判断是否达到目标棋局 
{
    for(int i=1;i<=4;i++)
    {
        if(a[i][1]==a[i][2]&&a[i][1]==a[i][3]&&a[i][1]==a[i][4]||a[1][i]==a[2][i]&&a[1][i]==a[3][i]&&a[1][i]==a[4][i]) return true;
    }
    if(a[1][1]==a[2][2]&&a[1][1]==a[3][3]&&a[1][1]==a[4][4]||a[1][4]==a[2][3]&&a[1][4]==a[3][2]&&a[1][4]==a[4][1]) return true;
    return false;
}
bool dfs(int k,int px1,int py1,int px2,int py2,int c)//c:上一次的颜色 pxpy:空白坐标 
{
    int tx1,ty1,tx2,ty2;
    if(k>cnt) return check();
    for(int i=1;i<=4;i++)
    {
        tx1=px1+fx[i],ty1=py1+fy[i],tx2=px2+fx[i],ty2=py2+fy[i];
        if(tx1>=1&&tx1<=4&&ty1>=1&&ty1<=4&&a[tx1][ty1]!=c)
        {
            swap(a[px1][py1],a[tx1][ty1]);
            if(dfs(k+1,tx1,ty1,px2,py2,(c==1?2:1))) return true;
            swap(a[px1][py1],a[tx1][ty1]);
        }
        if(tx2>=1&&tx2<=4&&ty2>=1&&ty2<=4&&a[tx2][ty2]!=c)
        {
            swap(a[px2][py2],a[tx2][ty2]);
            if(dfs(k+1,px1,py1,tx2,ty2,(c==1?2:1))) return true;
            swap(a[px2][py2],a[tx2][ty2]);
        }
    }
    return false;
}
int main()
{
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++) 
        {
            cin>>ch[i][j];
            if(ch[i][j]=='B') a[i][j]=1;
            if(ch[i][j]=='W') a[i][j]=2;
            if(!a[i][j]) 
            {
                if(!dx1) dx1=i,dy1=j;
                else dx2=i,dy2=j;
            }
        }
    }
    if(check())
    {
        printf("0");
        return 0;
    } 
    while(true)//迭代加深 
    {
        cnt++;
        if(dfs(1,dx1,dy1,dx2,dy2,1)) break;
        if(dfs(1,dx1,dy1,dx2,dy2,2)) break;
    }
    printf("%d",cnt);
    return 0;
}