#include<cstdio>#include<cstring>#include<queue>#include<iostream>using namespace std;const int hashn = 999997;int hash[hashn];struct node{    int s[3][3];};struct node1{    node point;    int step;    int x, y;};queue<node1> q;node dest = {1,2,3,8,0,4,7,6,5};const int dx[] = {0, 0, 1, -1};const int dy[] = {-1, 1, 0, 0};bool operator == (node &x, node &y){    for(int i = 0; i < 3; i++)        for(int j = 0; j < 3; j++)            if(x.s[i][j] != y.s[i][j])    return false;    return true;}void bfs(){    while(!q.empty()){        node1 u = q.front(); q.pop();        for(int i = 0; i < 4; i++){            int x1 = u.x + dx[i];            int y1 = u.y + dy[i];            if(x1 < 0 || x1 >= 3 || y1 < 0 || y1 >= 3)    continue;            node now = u.point;            now.s[u.x][u.y] = now.s[x1][y1];            now.s[x1][y1] = 0;            if(now == dest){                cout << u.step + 1 << endl;                return;            }            int n = 0;            for(int j = 0; j < 3; j++)                for(int k = 0; k < 3; k++)                    n = n*10 + now.s[j][k];            int nn = n % hashn;            while(hash[nn] != n && nn < hashn){                if(hash[nn] == -1)    break;                nn++;            }            if(hash[nn] == -1){                node1 v;                hash[nn] = n;                v.point = now;                v.x = x1, v.y = y1;                v.step = u.step + 1;                q.push(v);            }        }    }}int main(){    memset(hash, -1, sizeof(hash));    char c;    node st;    int x0, y0, n = 0;    for(int i = 0; i < 3; i++)        for(int j = 0; j < 3; j++){             cin >> c;             if(c == ‘0‘){                 x0 = i; y0 = j;             }             st.s[i][j] = c - ‘0‘;             n = n*10 + st.s[i][j];        }    int nn = n % hashn;    hash[nn] = n;    node1 st0;    st0.point = st; st0.step = 0; st0.x = x0; st0.y = y0;    q.push(st0);    bfs();    return 0;}

#include<iostream>#include<cstring>#include<cstdio>using namespace std;int xx[5] = {0,0,0,1,-1};int yy[5] = {0,1,-1,0,0};int map[5][5],minn = 1000;//利用数组代表“黑、白、空” minn代表所求的最小步数 char s;void Dfs(int x,int y,int num,int b){    int m = 100000,i,j,k;    if(num >= minn)         return;    for(i = 1;i <= 4;i ++)    {        if(map[i][1] == map[i][2] && map[i][2] == map[i][3] && map[i][3] == map[i][4] && (map[i][4] == 1 || map[i][4] == 2))//行相同更新         m = num;        if(map[1][i] == map[2][i] && map[2][i] == map[3][i] && map[3][i] == map[4][i] && (map[4][i] == 1 || map[4][i] == 2))//列相同更新         m = num;    }    if(map[1][1] == map[2][2] && map[2][2] == map[3][3] && map[3][3] == map[4][4] && (map[4][4]==1 || map[4][4] == 2))//左上到右下相同更新         m = num;    if(map[4][1] == map[3][2] && map[3][2] == map[2][3] && map[2][3] == map[1][4] && (map[1][4]==1 || map[1][4] == 2))//右上到左下相同更新         m = num;    if(m < minn)//m在上面已经更新为当前接了 这里用m更新minn     {        minn = m;        return;//不用往后搜索了 因为后面不如现在优     }    for(i = 1;i <= 4;i ++)    {        int tx = x + xx[i];//横坐标更新        int ty = y + yy[i];//纵坐标更新        if(tx > 0 && tx <= 4 && ty > 0 && ty <= 4 && map[tx][ty] == b)//边界判断         {            map[x][y] = map[tx][ty];            map[tx][ty] = 0;//走完之后map[tx][ty]变空  map[x][y]变map[tx][ty]            if(b == 1)            b = 2;//黑白交替走 上次走黑 下次走白             else b = 1;            for(j = 1;j <= 4;j ++)//因为空格又不止一个 所以 找空格             for(k = 1;k <= 4;k ++)            if(!map[j][k])//空格的值为0                 Dfs(j,k,num+1,b);            map[tx][ty] = map[x][y];//回溯             map[x][y] = 0;            if(b == 1)  b = 2;            else    b = 1;        }    }}int main(){    int i,j;    for(i = 1;i <= 4;i ++)    for(j = 1;j <= 4;j ++)    {        cin >> s;        if(s == ‘W‘) map[i][j] = 1;//白棋         if(s == ‘B‘) map[i][j] = 2;//黑棋     }    for(i = 1;i <= 4;i ++)    for(j = 1;j <= 4;j ++)    if(!map[i][j])//空格     {        Dfs(i,j,0,1);//先走白棋         Dfs(i,j,0,2);//先走黑棋     }    cout<<minn<<endl;    return 0;}