BZOJ-1085: 骑士精神

搜索

Description

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

给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。

Input

第一行有一个正整数T（T<=10） 表示一共有T组数据 接下来有T个5*5的矩形。0表示白色骑士1表示黑色骑士，*表示空位。(每组数据间有空行)

Output

对每组数据都输出一行。如果能在15不以内（包括15）到达目标状态，则输出步数，否则输出“Bored!”没有引号。

Sample Input

2
10110
01*11
10111
01001
00000

01011
110*1
01110
01010
00100

Sample Output

7
Bored!

• 代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
char a[5][5];
char aim[5][5]={{'1','1','1','1','1'},{'0','1','1','1','1'},{'0','0','*','1','1'},{'0','0','0','0','1'},{'0','0','0','0','0'}};
int dir[8][2]={1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1,-2,-1};
int flag;
int cmp() //比较目标与现在是否一致
{
    int i,j;
    for(i=0;i<5;i++)
        for(j=0;j<5;j++)
        if(a[i][j]!=aim[i][j])
        return 0;
    return 1;
}
int jug(int nowstp,int needstp)//有几处不同,就最少要移动几次！
{
    int i,j,count=0;
    for(i=0;i<5;i++)
        for(j=0;j<5;j++)
        if(a[i][j]!=aim[i][j])
            count++;
    if(count+nowstp>needstp)//如果现在最少移动的步数加上已经走的步数大于了例举的最小步数，那么说明不止移动这么多步
        return 0;
    return 1;
}
void dfs(int nowx,int nowy,int nowstp,int needstp)//现在的位置，现在的步数，例举的最小步数
{
    if(nowstp==needstp)//如果现在的步数和例举步数相同并且和目标棋盘一致
    {
        if(cmp()==1)
            flag=1;
        return;
    }
    if(flag==1)
        return;
    for(int i=0;i<8;i++)
    {
        int nextx=nowx+dir[i][0];
        int nexty=nowy+dir[i][1];
        if(nextx>=0&&nextx<5&&nexty>=0&&nexty<5)
        {
            swap(a[nowx][nowy],a[nextx][nexty]);
            if(jug(nowstp,needstp)==1)
                dfs(nextx,nexty,nowstp+1,needstp);
            swap(a[nowx][nowy],a[nextx][nexty]);
        }
    }
}
int main()
{
    int t,i,j,step,x,y;
    scanf("%d",&t);
    while(t--)
    {
        flag=0;
        for(i=0;i<5;i++)
            scanf("%s",a[i]);
        for(i=0;i<5;i++)
            for(j=0;j<5;j++)
            if(a[i][j]=='*')
        {
            x=i;
            y=j;
        }
        for(step=0;step<=15;step++)
        {
            dfs(x,y,0,step);
            if(flag==1)
            {
                printf("%d\n",step);
                break;
            }
        }
        if(flag==0)
            printf("Bored!\n");
    }
    return 0;
}