题目大意：给定一个高度为$6$ 的数塔，问最少多少步能走成原始状态。大于$20$ 步直接输出“too difficult”!
每次只能将值为$0$ 的点与其左上，上方，下方，右下四个方向的一个点进行交换。
双向BFS
利用中间相遇法，从给定状态和原始状态出发进行BFS。
复杂度$O(4^{\frac{n}{2}})$ 。
代码如下：
#include <queue>
#include <cstdio>
#include <unordered_map>
#include <iostream>
using namespace std;
typedef long long ll;
int T,t,ans,p;
int fl[21]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5};
int e[6]={0,1,3,6,10,15};
ll pow[22];
ll sd=751637788911935;
unordered_map<ll,int>vis1,vis2;
struct node{
ll s;
int p,d;
node(ll S,int P,int D){
s=S;p=P;d=D;
}
};
queue<node>q1,q2;
ll swp(ll s,int p,int q){
if(p<q)swap(q,p);
ll tp=s%pow[p+1]/pow[p];
ll tq=s%pow[q+1]/pow[q];
ll t=s/pow[p+1]*pow[p+1]+tq*pow[p]
+s%pow[p]/pow[q+1]*pow[q+1]+tp*pow[q]+s%pow[q];
return t;
}
int bfs(ll s,int p){
vis1.clear();vis2.clear();
vis1[sd]=0;vis2[s]=0;
while(!q1.empty())q1.pop();
while(!q2.empty())q2.pop();
q1.push(node(sd,0,0));
q2.push(node(s,p,0));
while(!q1.empty()||!q2.empty()){
if(!q1.empty()){
node t=q1.front();q1.pop();
ll s=t.s;
int p=t.p,d=t.d;
if(vis2.count(s))
return d+vis2[s];
int pf=fl[p];
int f=fl[p]+1;
if(p-f>=e[pf-1]){
ll ts=swp(s,20-p,20-(p-f));
if(vis1.count(ts)==0){
vis1[ts]=d+1;
if(d<10)q1.push(node(ts,p-f,d+1));
}
}
if(p<15){
ll ts=swp(s,20-p,20-(p+f));
if(vis1.count(ts)==0){
vis1[ts]=d+1;
if(d<10)q1.push(node(ts,p+f,d+1));
}
}
if(p-f+1<e[f-1]){
ll ts=swp(s,20-p,20-(p-f+1));
if(vis1.count(ts)==0){
vis1[ts]=d+1;
if(d<10)q1.push(node(ts,p-f+1,d+1));
}
}
if(p<15){
ll ts=swp(s,20-p,20-(p+f+1));
if(vis1.count(ts)==0){
vis1[ts]=d+1;
if(d<10)q1.push(node(ts,p+f+1,d+1));
}
}
}
if(!q2.empty()){
node t=q2.front();q2.pop();
ll s=t.s;
int p=t.p,d=t.d;
if(vis1.count(s))
return d+vis1[s];
int pf=fl[p];
int f=fl[p]+1;
if(p-f>=e[pf-1]){
ll ts=swp(s,20-p,20-(p-f));
if(vis2.count(ts)==0){
vis2[ts]=d+1;
if(d<10)q2.push(node(ts,p-f,d+1));
}
}
if(p<15){
ll ts=swp(s,20-p,20-(p+f));
if(vis2.count(ts)==0){
vis2[ts]=d+1;
if(d<10)q2.push(node(ts,p+f,d+1));
}
}
if(p-f+1<e[f-1]){
ll ts=swp(s,20-p,20-(p-f+1));
if(vis2.count(ts)==0){
vis2[ts]=d+1;
if(d<10)q2.push(node(ts,p-f+1,d+1));
}
}
if(p<15){
ll ts=swp(s,20-p,20-(p+f+1));
if(vis2.count(ts)==0){
vis2[ts]=d+1;
if(d<10)q2.push(node(ts,p+f+1,d+1));
}
}
}
}
return -1;
}
int main(void){
pow[0]=1;
for(int i=1;i<=21;++i)
pow[i]=pow[i-1]*6;
scanf("%d",&T);
while(T--){
ll s=0,tot=0;
for(int i=1;i<=6;++i){
for(int j=0;j<i;++j){
scanf("%d",&t);
s=s*6+t;
if(t==0)p=tot;
tot++;
}
}
ans=bfs(s,p);
if(ans!=-1)printf("%d\n",ans);
else printf("too difficult\n");
}
}