难度： 绿（洛谷上是蓝，但我觉得不至于）

标签： 进制，最短路

观察到，棋盘最多有 $2^{16}=65536$ 种状态。对于每种状态，至多有 $24$ 种操作（实际上有相邻两点一样的，所以平均只有 $12$ 种）。对每种状态建一个点，从该点出发，向可以通过一次操作到达的点连一条长度为 $1$ 的有向边。这样，你就得到了一个大约有 $6.5\times 10^4$ 个点，$8\times10^5$ 条有向边的图。直接跑 Dijkstra 即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int m=0,t,d[20],dis[65600],vis[65600],u,v,st,en;
vector<int> e[65600];
struct node{
	int u,dis;
	bool operator> (const node& a) const{return dis>a.dis;}
}k;
priority_queue<node,vector<node>,greater<node> > q;
map<string,int> mp;
string s,p;
int main(){
	while(!d[16]){
		s="1111111111111111";
		for(int i=0;i<16;i++) s[i]=char(d[i]+'0');
		mp[s]=++m;
		d[0]++;
		for(int i=0;i<16;i++){
			d[i+1]+=d[i]/2;
			d[i]%=2;
		}
	}
	memset(d,0,sizeof(d));
	while(!d[16]){
		s="1111111111111111";
		for(int i=0;i<16;i++) s[i]=char(d[i]+'0');
		for(int i=0;i<=12;i+=4){
			for(int j=i;j<i+3;j++){
				p=s;
				swap(p[j],p[j+1]);
				if(p==s) continue;
				e[mp[s]].push_back(mp[p]);
			}
		}
		for(int i=0;i<4;i++){
			for(int j=i;j<12;j+=4){
				p=s;
				swap(p[j],p[j+4]);
				if(p==s) continue;
				e[mp[s]].push_back(mp[p]);
			}
		}
		d[0]++;
		for(int i=0;i<16;i++){
			d[i+1]+=d[i]/2;
			d[i]%=2;
		}
	}
	s="";
	for(int i=1;i<=4;i++) cin>>p,s=s+p;
	st=mp[s];
	s="";
	for(int i=1;i<=4;i++) cin>>p,s=s+p;
	en=mp[s];
	memset(dis,0x3f3f3f,sizeof(dis));
	dis[st]=0;
	k.u=st,k.dis=0;
	q.push(k);
	while(!q.empty()){
		u=q.top().u;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<int(e[u].size());i++){
			v=e[u][i];
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				k.u=v,k.dis=dis[v];
				q.push(k);
			}
		}
	}
	printf("%d",dis[en]);
	return 0;
}