给一个图， 目标位置是确定的， 问你能否在15步之内达到目标位置。
因为只有15步， 所以直接ida*
#include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ull unsigned long long
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, },{-,-},{-,-},{-,},{,-} };
int ans[][] =
{
{,,,,},
{,,,,},
{,,,,},
{,,,,},
{,,,,},
};
int a[][], flag;
int judge() {
for(int i = ; i<; i++) {
for(int j = ; j<; j++) {
if(a[i][j]!=ans[i][j])
return ;
}
}
return ;
}
int h() {
int ret = ;
for(int i = ; i<; i++) {
for(int j = ; j<; j++) {
if(ans[i][j]!=a[i][j])
ret++;
}
}
return ret;
}
int step;
int dfs(int d) {
if(d==step)
return judge();
for(int i = ; i<; i++) {
for(int j = ; j<; j++) {
if(a[i][j] == ) {
for(int k = ; k<; k++) {
int x = i+dir[k][];
int y = j+dir[k][];
if(x<||x>||y<||y>)
continue;
swap(a[i][j], a[x][y]);
if(d+h()<=step)
if(dfs(d+))
return ;
swap(a[i][j], a[x][y]);
}
}
}
}
return ;
}
int main()
{
int t;
cin>>t;
char s[];
while(t--) {
for(int i = ; i<; i++) {
scanf("%s", s);
for(int j = ; j<; j++) {
if(s[j] == '*')
a[i][j] = ;
else
a[i][j] = s[j]-'';
}
}
flag = ;
for(int i = ; i<=; i++) {
step = i;
if(dfs()) {
printf("%d\n", i);
flag = ;
break;
}
}
if(!flag)
cout<<"-1"<<endl;
}
return ;
}