Description

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。

解题报告

这题有两种方法，这里都列举

首先是IDA，但是本人太菜，估价没写对，参考了其他人的，即与目标不同位置的棋的个数.

然后迭代搜索，如果估价值超过了迭代的值就返回即可*

另一种是作死的双向bfs+map，闲着就手写了挂链，对起点正向做一遍bfs保存状态的步数，做7层，再从终点反向做8层合并答案即可

双向bfs

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <queue>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

typedef long long ll;

const int N=6;

struct node{

   int a[N][N],x,y,dep,l;

   node(){}

   node(int b[N][N],int _x,int _y,int _dep,int _l){

      for(int i=0;i<=5;i++)for(int j=0;j<=5;j++)a[i][j]=b[i][j];

      x=_x;y=_y;dep=_dep;l=_l;

   }

};

queue<node>q;

char s[7];int sa[N][N],mx[8]={1,-1,1,-1,2,-2,2,-2},my[8]={2,-2,-2,2,1,-1,-1,1};

int ta[N][N];

int f[N][N]={{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}};

const int mod=1000005;

int head[mod],nxt[mod<<2],de[mod<<2],num=0;ll to[mod<<2];

void add(int dep){

   ll sum=0;

   for(int i=1;i<=5;i++)

      for(int j=1;j<=5;j++)

         sum=sum*3+ta[i][j];

   int k=sum%mod;

   nxt[++num]=head[k];to[num]=sum;de[num]=dep;head[k]=num;

}

int query(){

   ll sum=0;

   for(int i=1;i<=5;i++)

      for(int j=1;j<=5;j++)

         sum=sum*3+ta[i][j];

   for(int i=head[sum%mod];i;i=nxt[i])

      if(to[i]==sum)return de[i];

   return -1;

}

int ans=16;

void bfs(bool op){

   int x,y,tx,ty,ntt;node now;

   while(!q.empty()){

      now=q.front();q.pop();

      x=now.x;y=now.y;

      if(!op && now.dep>=7)return ;

      if(op && now.dep>=8)return ;

      for(int i=1;i<=5;i++)

         for(int j=1;j<=5;j++)

            ta[i][j]=now.a[i][j];

      for(int i=0;i<8;i++){

         if(i==now.l)continue;

         tx=mx[i]+x;ty=my[i]+y;

         if(tx>5 || tx<1 || ty>5 || ty<1)continue;

         swap(ta[x][y],ta[tx][ty]);

         ntt=query();

         if(!op && ntt!=-1){

            swap(ta[x][y],ta[tx][ty]);

            continue;

         }

         if(!op)add(now.dep+1);

         if(op && ntt!=-1)ans=Min(ntt+now.dep+1,ans);

         q.push(node(ta,tx,ty,now.dep+1,i^1));

         swap(ta[x][y],ta[tx][ty]);

      }

   }

}

void Clear(){

   while(!q.empty())q.pop();

   memset(head,0,sizeof(head));

   num=0;ans=16;

}

void work()

{

   Clear();

   int x,y;

   for(int i=1;i<=5;i++){

      scanf("%s",s+1);

      for(int j=1;j<=5;j++){

         if(s[j]!='*')ta[i][j]=sa[i][j]=s[j]-'0';

         else ta[i][j]=sa[i][j]=2,x=i,y=j;

      }

   }

   add(0);

   q.push(node(sa,x,y,0,-1));

   bfs(0);

   for(int i=1;i<=5;i++)

      for(int j=1;j<=5;j++)

         ta[i][j]=f[i][j];

   int tmp=query();

   if(tmp!=-1){printf("%d\n",tmp);return ;}

   while(!q.empty())q.pop();

   q.push(node(f,3,3,0,-1));bfs(1);

   if(ans<16)cout<<ans<<endl;

   else puts("-1");

}

int main()

{

	int T;cin>>T;

    while(T--)work();

	return 0;

}

IDA*

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int N=6;

int f[N][N]={{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}};

char s[9];int li,mx[8]={1,-1,1,-1,2,-2,2,-2},my[8]={2,-2,-2,2,1,-1,-1,1};

bool flag;

bool check(int a[N][N]){

   for(int i=1;i<=5;i++)

      for(int j=1;j<=5;j++)

         if(a[i][j]!=f[i][j])return false;

   return true;

}

bool Pienough(int a[N][N],int x){

   int ret=0;

   for(int i=1;i<=5;i++)

      for(int j=1;j<=5;j++){

         if(f[i][j]==a[i][j])continue;

         ret++;if(ret+x>li)return false;

      }

   return true;

}

void dfs(int a[N][N],int x,int y,int dep){

   if(check(a)){flag=true;return ;}

   if(dep>=li)return ;

   if(flag)return ;

   int tx,ty;

   for(int i=0;i<8;i++){

      tx=x+mx[i];ty=y+my[i];

      if(tx>5 || tx<1 || ty>5 || ty<1)continue;

      swap(a[x][y],a[tx][ty]);

      if(Pienough(a,dep))dfs(a,tx,ty,dep+1);

      swap(a[x][y],a[tx][ty]);

   }

}

void work()

{

   int a[N][N],x,y;

   for(int i=1;i<=5;i++){

      scanf("%s",s+1);

      for(int j=1;j<=5;j++){

         if(s[j]!='*')a[i][j]=s[j]-'0';

         else a[i][j]=2,x=i,y=j;

      }

   }

   flag=false;

   for(li=0;li<=15;li++){

      dfs(a,x,y,0);

      if(flag){

         printf("%d\n",li);

         return ;

      }

   }

   puts("-1");

}

int main()

{

	int T;cin>>T;

    while(T--)work();

	return 0;

}