P2324

然而，本地测试在codeforce的IDE结果是相同的

#include <stdio.h>
#include <queue>
#include <map>
#include<string>
#include<cstring>
using namespace std;
const int N = 26;
char en[N]={'0'}, sta[N] = {'0','1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '0', '0', '*', '1', '1', '0', '0', '0', '0', '1', '0', '0', '0', '0', '0'};
struct node{
	char ma[N];
	int x;
	int t;
	node(const char* arr, int pos, int time) : x(pos), t(time){
		memcpy(ma, arr, sizeof(char) * N);
	}
};
int xx[8]={-7,-11,-9,-3,7,11,9,3};
bool check(int x,int i){
	int xn[8]={-2,-1,1,2,2,1,-1,-2},yn[8]={-1,-2,-2,-1,1,2,2,1};
	int nx=(x==5?5:x%5),ny=(x==5?x/5:x/5+1);
	if(nx+xn[i]>=1&&nx+xn[i]<=5&&ny+yn[i]>=1&&ny+yn[i]<=5){
		return true;
	}
	return false;
}
int bfs(int xn){
	map<string,int> map1, map2;
	queue<node> que1, que2;
	int i,j;
	map1[sta]=1;
	map2[en]=1;
	que1.push(node(sta,13,1));
	que2.push(node(en,xn,1));
	while(!que1.empty()&&!que2.empty()){
		node now1=que1.front(),now2=que2.front();
		for(i=0;i<8;i++){
			if(check(now1.x,i)&&now1.t<8){
				swap(now1.ma[now1.x],now1.ma[now1.x+xx[i]]);
				if(!map1[now1.ma]){
					map1[now1.ma]=now1.t+1;
					que1.push(node(now1.ma,now1.x+xx[i],now1.t+1));
					if(map2[now1.ma]){
						return now1.t+map2[now1.ma]-1;
					}
				}
				swap(now1.ma[now1.x],now1.ma[now1.x+xx[i]]);
			}
			if(check(now2.x,i)&&now2.t<8){
				swap(now2.ma[now2.x],now2.ma[now2.x+xx[i]]);
				if(!map2[now2.ma]){
					map2[now2.ma]=now2.t+1;
					que2.push(node(now2.ma,now2.x+xx[i],now2.t+1));
					if(map1[now2.ma]){
						return now2.t+map1[now2.ma]-1;
					}
				}
				swap(now2.ma[now2.x],now2.ma[now2.x+xx[i]]);
			}
		}
		que1.pop(),que2.pop();
	}
	return -1;
}
char read(){
	char c=getchar();
	while(c==' '||c=='\n'){
		c=getchar();
	}
	return c;
}
void print(char a[]){
	putchar('\n');
	int i;
	for(i=1;i<=25;i++){
		printf("%c",a[i]);
		if(i%5==0){
			putchar('\n');
		}
	}
	return ;
}
int main(){
	int T;
	int i,xn;
	scanf("%d",&T);
	while (T--){
		for (i = 1; i <= 25; i++){
			en[i]=read();
			if(en[i]=='*'){
				xn=i;
			}
		}
		printf("%d\n",bfs(xn));
	}
	return 0;
}