#define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <algorithm>#include <cstdio>#include <cstdlib>#include <queue>#include <cstring>#include <map>#include <set>using namespace std;const int maxn = 4;//可移动方向 int dir[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };struct Status {    //last = 1 : 黑子, last = 2 : 白子     //包括把16位3进制转换成一个十进制数的结果hash,移动步数step     int hash, step, last;      //hash:为了描述棋子的位置信息,但是不能重复     int map[maxn][maxn];} Map;/** h[1][x]记录黑子放的移动到达的信息* h[1][x]=false，表示还没有移动这个状态* h[1][x]=true, 表示之前已经到达过, 不用进队*/map<int, bool> h[3];queue<Status> que;                //BFS, 队列void input();                            //输入数据 void solve();                            //启动函数 bool judge(int r, int c);        //判断越界 bool check(Status a);              //判断是否满足目标状态 //移动一步，生成新的棋子位置, k 为移动方向 void Move(Status now, int r, int c, int k);void findSpace(const Status& now, int &r, int &c, int &r2, int &c2); //找到空格的位置 //把此时棋盘的状态, 全部用0,1,2表示每一位的三进制,转换成一个十进制int getHash(Status a);          //对当前棋盘的棋子设置HashCode  void BFS();                              //宽搜BFSvoid input(){    char s[10];    /*    * 把每一位的棋子 换成 空格-0,黑子-1, 白子-2 (三进制)    * 这是一个16位的3进制数, 对应一个十进制数, 然后通过哈希该    * 棋盘的十进制数, 则可找到对应的棋盘状态    */    for (int i = 0; i < maxn; i++)    {        scanf("%s", s);        for (int j = 0; j < maxn; j++) {            if (s[j] == ‘B‘) Map.map[i][j] = 1;            if (s[j] == ‘W‘) Map.map[i][j] = 2;        }    }}bool judge(int r, int c){    return (r >= 0 && r < maxn) && (c >= 0 && c < maxn);}bool check(Status a){    bool flag = true;    //横向连成4个     for (int i = 0; i < maxn; i++)    {        flag = true;        for (int j = 0; j < maxn - 1; j++) {            if (a.map[i][j] != a.map[i][j + 1]) {                flag = false;            }        }        if (flag) return true;    }    //纵向连成4个     for (int i = 0; i < maxn; i++)    {        flag = true;        for (int j = 0; j < maxn - 1; j++) {            if (a.map[j][i] != a.map[j + 1][i]) {                flag = false;            }        }        if (flag) return true;    }    flag = true;    for (int i = 0; i < maxn - 1; i++) {        if (a.map[i][i] != a.map[i + 1][i + 1]) {            flag = false;        }    }    if (flag) return true;    flag = true;    for (int i = maxn - 1; i > 0; i--) {        if (a.map[i][i] != a.map[i - 1][i - 1]) {            flag = false;        }    }    if (flag) return true;    //都没有连成4子, false     return false;}//全部用0,1,2表示每一位的三进制,转换成一个十进制 //用了Hash查找 int getHash(Status a){    int res = 0;    int k = 1;    for (int i = 0; i < 4; i++) {        for (int j = 0; j < 4; j++) {            res += a.map[i][j] * k;            k *= 3;        }    }    return res;}void findSpace(const Status& now, int &r1, int &c1, int &r2, int &c2){    for (int i = 0; i < maxn; i++)    {        for (int j = 0; j < maxn; j++) {            if (!now.map[i][j])            {                if (r1 == -1 && c1 == -1) {                    r1 = i; c1 = j;                }                else {                    r2 = i; c2 = j;                }            }        }    }}/*每移动 一步,都需要对其进行* 1.是否越界检查* 2.移动棋子, 并标志移动, 并设置下一次移动的棋子种类* 3.是否完成目标检查* 4.未完成 则 设置新棋盘的HashCode* 5.检查该棋子状态 是否出现过, 没有则入队，并标志为出现过*移动一步，生成新的棋子位置, k 为移动方向*/void Move(Status now, int r, int c, int k){    Status tmp = now;    int tmpx = r + dir[k][0];    int tmpy = c + dir[k][1];    //判断是否越界 || 先后手, 不能两次都移动自己的子    //(如,第一次移动白子,第二次,白子能够移动还移动白子,是错误行为     if (!judge(tmpx, tmpy) || tmp.map[tmpx][tmpy] == tmp.last)        return;    tmp.last = 3 - tmp.last;       //取反,上次白子(1), 这次就黑子(2)    swap(tmp.map[tmpx][tmpy], tmp.map[r][c]);  //交换棋子和空白位置     tmp.hash = getHash(tmp);       //重新设置hashCode    tmp.step++;                              //移动成功,步数+1    if (check(tmp)) {        printf("%d\n", tmp.step);        exit(0);                   //结束整个程序     }//表示tmp.last这个种类, 单独的某个棋子 当前的状态-是否移动过     //false-没有移动过，可以入队     if (!h[tmp.last][tmp.hash])    {        h[tmp.last][tmp.hash] = true;  //标志此状态已经出现过                que.push(tmp);                                 //入队     }}void BFS(){    Map.hash = getHash(Map);    //首状态棋盘对应的HashCode    //因为谁先下都行，所以两个棋子都应该入队         Map.last = 1;    que.push(Map);    Map.last = 2;  //黑    que.push(Map);    while (!que.empty())    {        Status now;        now = que.front();        que.pop();        int r1 = -1, c1 = -1, r2 = -1, c2 = -1;        findSpace(now, r1, c1, r2, c2);  //找到空格位置         //一个棋盘有两个空格,所以两个一起来搜索四个方向          for (int k = 0; k < maxn; k++) {            Move(now, r1, c1, k);            Move(now, r2, c2, k);        }    }}void solve(){    input();    BFS();}int main(){    solve();    return 0;}