骑士精神 (codevs 2449)

题目描述 Description

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。

给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：

为了体现出骑士精神，他们必须以最少的步数完成任务。

输入描述 Input Description

第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。

输出描述 Output Description

对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

样例输入 Sample Input

01*11

110*1

样例输出 Sample Output

-1

数据范围及提示 Data Size & Hint

见题面

/*

  迭代加深搜索

  加了两个剪枝，跑了47ms

  ①刚交换完的两个点不能立马交换回来

  ②如果当前有c个点与目标棋局不同，且已经走了t-1步，

    如果c+t-2>limit ,则该方案不可行

*/

#include<cstdio>

#include<iostream>

#define M 6

using namespace std;

int goal[M][M]={{,,,,,},{,,,,,},{,,,,,},

                {,,,,,},{,,,,,},{,,,,,}};

int aa[]={,,-,-,,,-,-};

int bb[]={,-,,-,,-,,-};

int a[M][M],map[M][M],num[M][M],ans;

int check()

{

    int tot=;

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

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

        if(a[i][j]!=goal[i][j])

          tot++;

    return tot;

}

void fuzhi()

{

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

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

        a[i][j]=map[i][j];

}

void dfs(int sx,int sy,int x,int y,int t,int limit)

{

    int c=check();

    if(!c)

    {

        ans=min(ans,t-);

        return;

    }

    if(t+c->limit)return;//①

    if(t>limit)return;

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

    {

        int xx=x+aa[i];

        int yy=y+bb[i];

        if(xx>=&&xx<=&&yy>=&&yy<=&&!(xx==sx&&yy==sy))//②

        {

            swap(a[x][y],a[xx][yy]);

            dfs(x,y,xx,yy,t+,limit);

            swap(a[x][y],a[xx][yy]);

        }

    }

}

void init()

{

    int qx,qy;

    ans=;

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

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

      {

          char c;

          cin>>c;

          if(c=='*')map[i][j]=,qx=i,qy=j;

          else map[i][j]=c-'';

      }

    for(int k=;k<=;k++)

    {

        fuzhi();

        dfs(qx,qy,qx,qy,,k);

        if(ans<){printf("%d\n",ans);return;}

    }

    printf("-1\n");

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)init();

    return ;

}