洛谷 P2324 [SCOI2005]骑士精神 题解【估价】【搜索】【状态压缩】

点击量：185

    万能的估价啊。。。

目录

题目描述

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

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

 

输入输出格式

输入格式：

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

 

输出格式：

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

 

输入输出样例

输入样例#1：

2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100

输出样例#1：

7
-1

说明

样例中第二个数据的初始情况对应该图：

题解：

    这样的题面，除了搜索应该没什么更适合的方法了。因为一个空格可供最多8个方向的马跳过来，我们可以转化成一个空格可以和周围的8个马交换位置，也就是这里跳的是空格而不是马。

    不过一步最多可能会引出8个状态，因此复杂度上界是$ O(8^15)$，远大于1s的时限，因此考虑剪枝。

    首先我们知道，如果当前状态是从某个方向跳过来的，那就不能让它跳回去，这个题没有办法判重，所以尽可能用这种方法避免一定不合法/不是最优的情况。

    因为一个棋盘只可能有黑、白、空三种状态。我们把空的归为白色，特判就好了。这样最终状态就是

11111
01111
00011
00001
00000

    棋盘上只有25个格子，因此可以状态压缩。如果我们把(1,1)的位置放在第0位，那么(x,y)位置就被放在第5×(x-1)+y-1位。最终的状态是

0000010000110001111011111 (2)=549855 (10)

    如果当前状态与目标状态相差超过ans-num（已知最优解与已经走过的步数之差），差值即popcount(now^goal)，就不用搜索了。因为当前状态距离目标状态的最理想情况都还有超过ans-num步要走，就算搜到了也无法更新最优答案。这个就是A*中的估价函数，表示最优情况还要多少的代价才能到终点，如果最优情况都比已知解要劣，那么就提前剪枝。

    按位读入不要读反了。为了使与来时的方向不同，我们可以在X,Y数组中对称地存，像这样：

int X[10]={1,2,2,1,-1,-2,-2,-1};
int Y[10]={2,1,-1,-2,2,1,-1,-2};

    每次从i跳过来，就不能从7-i跳回去了。不过剪枝效果没有估价函数明显。

Code：

#include<cstdio>
#include<cstring>
int now=0,End=549855;
char c[10][10];
inline int popcnt(int x)
{
    int cnt=0;
    while(x)
    {
        cnt++;
        x-=(x&(-x));
    }
    return cnt;
}
int X[10]={1,2,2,1,-1,-2,-2,-1};
int Y[10]={2,1,-1,-2,2,1,-1,-2};
int num=-1;
int ans,flag;
void dfs(int x,int y,int from)
{
    num++;
    int tmp=popcnt(now^End);
    if(tmp>ans-num)//估价函数剪枝
    {
        num--;
        return;
    }
    if(x==3&&y==3&&tmp==0)//特判空白在哪，因为空白被设为白色旗子。
    {
        ans=ans<num?ans:num;
        flag=1;
        num--;
        return;
    }
    int r=now;
    int pla,planow=(x-1)*5+y;
    for(register int i=0;i<8;i++)
        if(i!=from&&x+X[i]>0&&x+X[i]<6&&y+Y[i]>0&&y+Y[i]<6)//在棋盘内且没有回跳
        {
            pla=((x+X[i]-1)*5)+y+Y[i];
            tmp=((now>>pla-1)&1);

            if(tmp)
            {
                now^=(1<<pla-1);
                now^=(1<<planow-1);
            }
            dfs(x+X[i],y+Y[i],8-i-1);
            now=r;
        }
    num--;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        flag=0;
        now=0;
        int sx,sy;
        for(int i=1;i<=5;i++)
            scanf("%s",c[i]);
        for(int i=5;i>=1;i--)
            for(int j=4;j>=0;j--)
            {
                if(c[i][j]=='*')
                {
                    sx=i;
                    sy=j+1;
                }
                now<<=1;
                now|=(c[i][j]=='1');
            }
        ans=15;
        dfs(sx,sy,-1);
        if(!flag)
            puts("-1");
        else
            printf("%d\n",ans);
    }
    return 0;
}