[文章目录]
Description
在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。步数>15输出-1
这题好像网上都是IDA*，然而我学了一天的搜索，愣是怀疑人生了。（另外IDA*是个毛???）
由于状态可以表示，并且起末状态已知，我们可以双向广搜，将连终点的一边的改成深搜。连起点一边的迭代加深搜索。然后，期望时间复杂度O(T*3^7)。理论上，感觉两遍bfs也可行，不过主要是不知道队列要开多大，就写成dfs了。另外层数固定，且非常小，不用考虑系统栈的问题。状态用两个int，一个二进制存黑白，另一个存当前空白位置。注意，一定将存黑白的int在now上的二进制赋值成一样的数，不然无法从map里找到该状态。注意：编号与坐标与状态的关系，恩，WA了*3。148ms
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> pr;
pr root;
map<pr,int>v;
int T,ans,lim;
char st[30];
bool flag;
int dx[]={-1,1,-1,1,-2,2,-2,2},dy[]={2,-2,-2,2,1,-1,-1,1};
void output(pr x)//调试
{
int a=x.first,b=x.second;
for(int i=0;i<25;i++)
{
if(i==b-1) putchar('*');
else if(a&(1<<i)) putchar('1');
else putchar('0');
if(i%5==4) puts("");
}
puts("");
}
void initial(pr x,int step,int pre)
{
if(step>9) return ;
int now=x.second,xx=(now-1)/5+1,yy=(now-1)%5+1;//各种小BUG
for(int i=0;i<8;i++)
if(i!=pre&&xx+dx[i]>0&&xx+dx[i]<=5&&yy+dy[i]>0&&yy+dy[i]<=5)
{
int tmp=(xx+dx[i]-1)*5+yy+dy[i];
if(x.first&(1<<tmp-1))
{
x.first=x.first|(1<<now-1);
x.second=tmp;
x.first=x.first&(~(1<<x.second-1));//使得关键字相同
if(!v[x]) v[x]=step;
else v[x]=min(v[x],step);
initial(x,step+1,i^1);
x.first=x.first|(1<<tmp-1);
x.second=now;
}
else
{
x.first=x.first&(~(1<<now-1));
x.second=tmp;
x.first=x.first&(~(1<<x.second-1));//使得关键字相同
if(!v[x]) v[x]=step;
else v[x]=min(v[x],step);
initial(x,step+1,i^1);
x.first=x.first&(~(1<<tmp-1));
x.second=now;
}
}
}
void dfs(pr x,int step,int pre)
{
x.first=x.first&(~(1<<x.second-1));//使得关键字相同
if(v[x]) {ans=lim+v[x]-1,flag=0; return ;}
if(step>lim) return ;
int now=x.second,xx=(now-1)/5+1,yy=(now-1)%5+1;
for(int i=0;i<8;i++)
if(i!=pre&&xx+dx[i]>0&&xx+dx[i]<=5&&yy+dy[i]>0&&yy+dy[i]<=5&&flag)
{
int tmp=(xx+dx[i]-1)*5+yy+dy[i];
if(x.first&(1<<tmp-1))
{
x.first=x.first|(1<<now-1);
x.second=tmp;
dfs(x,step+1,i^1);
x.first=x.first|(1<<tmp-1);
x.second=now;
}
else
{
x.first=x.first&(~(1<<now-1));
x.second=tmp;
dfs(x,step+1,i^1);
x.first=x.first&(~(1<<tmp-1));
x.second=now;
}
}
}
void initialize()//从终点搜索8层
{
root.second=13;
root.first=549855;
v[root]=1;
initial(root,2,8);
}
int main()
{
initialize();
scanf("%d",&T);
while(T--)
{
pr tmp; tmp.first=0;
for(int i=1;i<=5;i++)
{
scanf("%s",st+1);
for(int j=1;j<=5;j++)
{
if(st[j]=='1') tmp.first|=(1<<(i-1)*5+j-1);
else if(st[j]=='*') tmp.second=(i-1)*5+j;
}
}
ans=-1; flag=1;
for(lim=0;flag&&lim<8;lim++) dfs(tmp,1,8);//迭代加深 IDFS 最大 搜7层
printf("%d\n",ans);
}
return 0;
}