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

作者: wjyyy 分类: 估价,搜索,状态压缩,解题报告 发布时间: 2018-08-02 19:51

点击量:96

 

    万能的估价啊。。。

 

题目描述

在一个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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */