【题目】
传送门
题目描述：
在一个
5
×
5
5×5
5×5 的棋盘上有
12
12
12 个白色的骑士和
12
12
12 个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为
1
1
1 ，纵坐标相差为
2
2
2 或者横坐标相差为
2
2
2 ，纵坐标相差为
1
1
1 的格子）移动到空位上。
给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：
为了体现出骑士精神，他们必须以最少的步数完成任务。
输入格式：
第一行有一个正整数
t
t
t（
t
t
t ≤
10
10
10），表示一共有
t
t
t 组数据。
接下来有
t
t
t 个
5
×
5
5×5
5×5 的矩阵，
0
0
0 表示白色骑士，
1
1
1 表示黑色骑士，
∗
*
∗ 表示空位。两组数据之间没有空行。
输出格式：
对于每组数据都输出一行。如果能在
15
15
15 步以内（包括
15
15
15 步）到达目标状态，则输出步数，否则输出
−
1
-1
−1 。
样例数据：
输入 2 10110 01*11 10111 01001 00000 01011 110*1 01110 01010 00100
输出 7 -1
备注：
【样例说明】 样例中第二个数据的初始情况对应该图：
【分析】
题解：IDA*（我觉得就是迭代加深和 A* 的结合）
看到数据范围最多移动
15
15
15 次，很容易想到搜索，但爆搜显然是不行的，要想办法优化，于是想到这几个搜索优化
首先是由于最多走
15
15
15 步，很容易想到迭代加深，不断加大深度来判断当前的深度是否合法
然后就是用 A* 优化，这道题的估价函数是很好写的，由于每次移动最多使一个骑士到位，所以统计一下当前没有到位的骑士就是估计值了
直接用骑士来
d
f
s
dfs
dfs 不太好做，我们就想到用空格的移动来
d
f
s
dfs
dfs（因为每次移动空格的位置都会变）
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std
;
int h
,flag
,a
[10][10];
int tx
[10]={0,1,1,2,2,-2,-2,-1,-1};
int ty
[10]={0,2,-2,1,-1,1,-1,2,-2};
int goal
[7][7]={
{0,0,0,0,0,0},
{0,1,1,1,1,1},
{0,0,1,1,1,1},
{0,0,0,2,1,1},
{0,0,0,0,0,1},
{0,0,0,0,0,0}
};
int eva()
{
int i
,j
,num
=0;
for(i
=1;i
<=5;++i
)
for(j
=1;j
<=5;++j
)
if(a
[i
][j
]!=goal
[i
][j
])
num
++;
return num
;
}
void A_star(int x
,int y
,int dep
)
{
if(dep
==h
)
{
if(!eva())
flag
=true;
return;
}
int i
,xx
,yy
;
for(i
=1;i
<=8;++i
)
{
xx
=x
+tx
[i
];
yy
=y
+ty
[i
];
if(xx
>=1&&xx
<=5&&yy
>=1&&yy
<=5)
{
swap(a
[x
][y
],a
[xx
][yy
]);
if(eva()+dep
<=h
)
A_star(xx
,yy
,dep
+1);
swap(a
[x
][y
],a
[xx
][yy
]);
}
}
}
int main()
{
char c
;
int n
,i
,j
,sx
,sy
;
scanf("%d",&n
);
while(n
--)
{
for(i
=1;i
<=5;++i
)
{
for(j
=1;j
<=5;++j
)
{
cin
>>c
;
a
[i
][j
]=c
-'0';
if(c
=='*') a
[i
][j
]=2,sx
=i
,sy
=j
;
}
}
if(!eva()) {printf("0\n");continue;}
flag
=0;
for(h
=1;h
<=15;++h
)
{
A_star(sx
,sy
,0);
if(flag
) {printf("%d\n",h
);goto end
;}
}
printf("-1\n");
end
:;
}
return 0;
}
