肯定是搜索题无疑问，
首先要求在15步以内（包括15步）到达目标状态，也就是限定了搜索的深度，于是我们用dfs更合适
但这样复杂度仍然太大，原因就是我们在搜索中做了很多很不优的尝试
考虑当前状态若与目标状态有x处不相同，我们至少要移动x-1步才能成功
如果当前移动次数+x-1>=已找到的最小移动次数（没找到就为16），那么再往下移动肯定是没有意义的
这样我们就可以构造出估价函数，大大优化时间复杂度
const dx:array[..] of integer=(-,,-,,-,-,,);
dy:array[..] of integer=(,,-,-,-,,-,);
en:array[..,..] of integer=((,,,,),
(,,,,),
(,,-,,),
(,,,,),
(,,,,));
var num,a:array[..,..] of integer;
k,min,x0,y0,x1,y1,i,j,t:longint;
s:string; procedure swap(var a,b:integer);
var c:integer;
begin
c:=a;
a:=b;
b:=c;
end; function check:longint;
var i,j:integer;
begin
check:=;
for i:= to do
for j:= to do
if a[i,j]<>en[i,j] then inc(check);
exit(check-);
end; procedure dfs(x,y,d:integer);
var xx,yy,i,p:integer;
begin
if d>=min then exit;
p:=check;
if p=- then
begin
min:=d;
exit;
end;
if p+d>=min then exit;
for i:= to do
begin
xx:=x+dx[i];
yy:=y+dy[i];
if (xx>) and (xx<=) and (yy>) and (yy<=) then
begin
swap(a[x,y],a[xx,yy]);
dfs(xx,yy,d+);
swap(a[x,y],a[xx,yy]);
end;
end;
end; begin
readln(t);
while t> do
begin
min:=;
k:=;
for i:= to do
begin
readln(s);
for j:= to do
begin
if s[j]='*' then
begin
x0:=i;
y0:=j;
a[i,j]:=-;
end
else a[i,j]:=ord(s[j])-;
end;
end;
dfs(x0,y0,);
if min= then writeln(-) else writeln(min);
dec(t);
end;
end.