[BZOJ]1085 骑士精神(SCOI2005)

时间：2023-03-08 22:55:52
[BZOJ]1085 骑士精神(SCOI2005)

　　这种鲜明的玄学风格很明显就是十几年前的题目。

Description

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

　　[BZOJ]1085 骑士精神(SCOI2005)

Input

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

Output

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

Sample Input

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

Sample Output

　　7
　　-1

HINT

　　T<=10。

Solution

　　拿到这道题应该没有别的想法吧，于是我们直接开始往搜索去想。

　　由于步数最多只有15，所以最暴力的暴力的时间复杂度为O(T*25*815)。

　　如果用A*算法解决这道题，估价函数为不符合答案的格子个数，如果剩余步数小于这个值，那么这个状态一定不能在15步内走到答案。

　　复杂度似乎可以不用乘上25，所以理论时间复杂度上限为O(T*815)。

　　所以A*算法就是这么神奇地通过该题的，网络上题解有很多，小C就不再赘述。

　　都是玄学。

　　所以小C还是介绍一下自己的折半搜索做法吧。

　　从目标状态往前搜8步，用一个map把每个状态hash的答案存下来。

　　从每个起始状态往后搜7步，对于每个状态到map查找并更新答案。

　　理论时间复杂度O(25*88*log(state)+T*25*87*log(state))。

　　加一个判重的剪枝，可以跑得飞快。

　　map还可以用O(1)的，hash还可以动态维护。所以时间复杂度可以优化到O(88+T*87)。

　　而且每个状态不是满的8种转移方式，实际的时间复杂度远远小于上限。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

#define ll unsigned long long

using namespace std;

typedef char matr[][];

const int fx[][]={{,},{,-},{-,},{-,-},{,},{,-},{-,},{-,-}};

map <ll,int> mp;

matr c,d;

int cx,cy,dx,dy,ans,t;

inline int read()

{

    int n=,f=; char c=getchar();

    while (c<'' || c>'') {if(c=='-')f=-; c=getchar();}

    while (c>='' && c<='') {n=n*+c-''; c=getchar();}

    return n*f;

}

ll geth(matr c,int x,int y)

{

    ll h=;

    register int i,j;

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

        for (j=;j<=;++j) h=h*+c[i][j]-'';

    h=h*+x-; h=h*+y-;

    return h;

}

bool check(int x,int y) {return x<||x>||y<||y>;}

void dfs1(int stp)

{

    ll h=geth(c,cx,cy);

    if (mp[h]&&mp[h]<=stp) return;

    mp[h]=stp;

    if (stp>) return;

    register int i,ncx,ncy;

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

    {

        ncx=cx+fx[i][];

        ncy=cy+fx[i][];

        if (check(ncx,ncy)) continue;

        swap(c[cx][cy],c[ncx][ncy]);

        swap(cx,ncx); swap(cy,ncy);

        dfs1(stp+);

        swap(cx,ncx); swap(cy,ncy);

        swap(c[cx][cy],c[ncx][ncy]);

    }

}

void dfs2(int stp)

{

    ll h=geth(d,dx,dy);

    if (mp[h]) ans=min(ans,stp+mp[h]-);

    if (stp>) return;

    register int i,ndx,ndy;

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

    {

        ndx=dx+fx[i][];

        ndy=dy+fx[i][];

        if (check(ndx,ndy)) continue;

        swap(d[dx][dy],d[ndx][ndy]);

        swap(dx,ndx); swap(dy,ndy);

        dfs2(stp+);

        swap(dx,ndx); swap(dy,ndy);

        swap(d[dx][dy],d[ndx][ndy]);

    }

}

int main()

{

    register int i,j;

    t=read();

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

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

                 if (i<j||i==j&&i<=) c[i][j]='';

            else if (i>j||i==j&&i>=) c[i][j]='';

    cx=cy=; dfs1();

    while (t--)

    {

        ans=;

        for (i=;i<=;++i) scanf("%s",d[i]+);

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

        {

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

                if (d[i][j]=='*') {dx=i; dy=j; d[i][j]=''; break;}

            if (j<=) break;

        }

        dfs2();

        printf("%d\n",ans==?-:ans);

    }

}

Last Word

　　不过仔细想想玄学题目并不只是十几年前的专利啊，比如FJOI的D2T2……

相关文章