题目链接 : BZOJ 1085
题目分析 :
本题中可能的状态会有 (2^24) * 25 种状态，需要使用优秀的搜索方式和一些优化技巧。
我使用的是 IDA* 搜索，从小到大枚举步数，每次 DFS 验证在当前枚举的步数之内能否到达目标状态。
如果不能到达，就枚举下一个步数，重新搜索，即使某些状态在之前的 DFS 中已经搜索过，我们仍然搜索。
并且在一次 DFS 中，我们不需要判定重复的状态。
在 IDA* 中，重要的剪枝优化是 估价函数 ，将一些不可能存在可行解的枝条剪掉。
如果估价函数写得高效，就能有极好的效果。我们写估价函数的原则是，绝对不能剪掉可能存在可行解的枝条。
因此，在预估需要步数时，应让估计值尽量接近实际步数，但一定不能大于实际需要的步数。
本题的一个很有效的估价函数是，比较当前状态的黑白骑士与目标状态的黑白骑士有多少不同，我们把这个值作为估价函数值，因为每一步最多将当前状态的一个骑士改变为与目标状态相同。但是应该注意的是，空格所在的格子不要算入其中。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MaxStep = ;
const int Dx[] = {, , -, -, , , -, -}, Dy[] = {, -, , -, , -, , -};
int Te, Ans;
char Str[];
struct ES
{
int num, pos;
bool operator == (const ES &e) const {
return (num == e.num) && (pos == e.pos);
}
} S, T;
inline bool Inside(int x, int y) {
if (x < || x > ) return false;
if (y < || y > ) return false;
return true;
}
void Print(ES x) {
for (int i = ; i < ; ++i) {
for (int j = ; j < ; ++j) {
if (x.pos == (i * + j)) printf("*");
else {
if (x.num & ( << (i * + j))) printf("");
else printf("");
}
}
printf("\n");
}
}
inline int Expect(ES x) {
int Temp, Cnt;
Temp = x.num ^ T.num;
Cnt = ;
if (x.pos != T.pos) {
if (Temp & ( << T.pos)) --Cnt;
if (Temp & ( << x.pos)) --Cnt;
}
while (Temp) {
++Cnt;
Temp -= Temp & -Temp;
}
return Cnt;
}
bool DFS(ES Now, int Step, int Limit) {
if (Now == T) return true;
if (Step == Limit) return false;
if (Expect(Now) > Limit - Step) return false;
int x, y, xx, yy;
ES Next;
x = Now.pos / ; y = Now.pos % ;
for (int i = ; i < ; i++) {
xx = x + Dx[i]; yy = y + Dy[i];
if (!Inside(xx, yy)) continue;
Next = Now;
Next.pos = xx * + yy;
Next.num &= ( << ) - - ( << (xx * + yy));
if (Now.num & ( << (xx * + yy))) Next.num |= ( << (x * + y));
if (DFS(Next, Step + , Limit)) return true;
}
return false;
}
int IDAStar(ES S) {
if (S == T) return ;
for (int i = ; i <= MaxStep; ++i)
if (DFS(S, , i)) return i;
return -;
}
int main()
{
scanf("%d", &Te);
T.num = ; T.pos = ;
for (int Case = ; Case <= Te; ++Case) {
S.num = ;
for (int i = ; i < ; ++i) {
scanf("%s", Str);
for (int j = ; j < ; ++j) {
if (Str[j] == '') S.num |= ( << (i * + j));
if (Str[j] == '*') S.pos = i * + j;
}
}
Ans = IDAStar(S);
printf("%d\n", Ans);
}
return ;
}