解题思路

题意：有一个棋盘，上面放了黑色和白色两种颜色的棋子，一次只能交换相邻两个位置的棋子，然后给出起始状态和目的状态，问最少能经过多少步到达，并且给出具体的操作。

思路：宽搜就行了，如果单向能过就单向搜就行了，如果不过就双向。由于只有$16$个位置，所以状态数为$2^16$，完全可以把棋盘看成一个$int$进行判重。然后记录步骤的时候我们用$16bit$表示棋盘状态，用$8bit$表示操作，因为操作是$R1,C1,R2,C2$ 其中它们都是$[1,4]$那么两位就能表示一个数了，所以$4$个数字只需要$8bit$，我们用低$8$位表示操作，高$16$位表示棋盘状态。具体的操作可以看代码。

标程

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<queue>
using namespace std;
#define LL long long
 
int d[1<<16|1] , s , t , now;
int pre[1<<16|1];
int Move[2][4] = { { -1 , 0 , 1 , 0 } , { 0 , 1 , 0 , -1 } };
char buffer[10];
 
int row(int st)
{
        return st / 4;
}
 
int column(int st)
{
        return st % 4;
}
 
int to_loc(int r,int c)
{
        return r*4+c;
}
 
bool inRange(int r,int c)
{
        if (r < 0 || r >= 4 || c <0 || c >= 4) return false;
        return true;
}
 
void init()
{
        memset(pre,-1,sizeof(pre));
        memset(d,-1,sizeof(d));
}
 
void input()
{
        s = t = 0;
        int base = 1;
        for (int j = 0 ; j < 4 ; ++j) 
        {
                if (buffer[j]=='1') s += base;
                base *= 2;
        }
        for (int i = 1 ; i < 4 ; ++i)
        {
                scanf("%s",buffer);
                for (int j = 0 ; j < 4 ; ++j)
                {
                        if (buffer[j]=='1') s += base;
                        base *= 2;
                }
        }
        base = 1;
        for (int i = 0 ; i < 4 ; ++i)
        {
                scanf("%s",buffer);
                for (int j = 0 ; j < 4 ; ++j)
                {
                        if (buffer[j]=='1') t += base;
                        base *= 2;
                }
        }
}
 
void output(int cur)
{
        if (cur==s) return;
        output(pre[cur]>>8);
        printf("%d %d %d %d\n",(pre[cur]>>6&3)+1,(pre[cur]>>4&3)+1,(pre[cur]>>2&3)+1,(pre[cur]&3)+1);
}
 
void solve()
{
        queue<int> q;
        q.push(s);
        d[s] = 0;
        while (q.size())
        {
                int st = q.front(); q.pop();
                if (st==t) break;
                for (int r = 0 ; r < 4 ; ++r)
                {
                        for (int c = 0 ; c < 4 ; ++c)
                        {
                                for (int i = 0 ; i < 4 ; ++i)
                                {
                                        now = st;
                                        int rr = r+Move[0][i];
                                        int cc = c+Move[1][i];
                                        if (!inRange(rr,cc)) continue;
                                        int k1 = to_loc(r,c);
                                        int k2 = to_loc(rr,cc);
                                        int tmp = ((1<<k2&now)>>k2<<k1)+((1<<k1&now)>>k1<<k2);
                                        now -= (1<<k1&now)+(1<<k2&now);
                                        now += tmp;
                                        if (d[now]==-1)
                                        {
                                                d[now] = d[st]+1;
                                                q.push(now);
                                                pre[now] = (st<<8)+(r<<6)+(c<<4)+(rr<<2)+cc;
                                        }
                                }
                        }
                }
        }
        printf("%d\n",d[t]);
        output(t);
}
 
int main()
{
        while (scanf("%s",buffer)==1)
        {
                init();
                input();
                solve();
        }
}