题解 P1930 【亚瑟王的宫殿】

· · 题解

造出来一个数据结果hack了所有题解... 你们这是思想僵化的表现啊

这篇题解分两块，先讲讲此题思路，再对于其他题解的错误点进行详细分析。

一.本题思路及细节处理

0. 首先亚瑟王实在是太可爱了QwQ，吾王万岁！

看什么看，没见过亚瑟王Saber吗。

1. 这题如果不讲数据范围，就会让人十分难以下手：

首先集合点是本题核心，所有操作都是基于集合点确定的情况下。但他不告诉你点在哪里。但一看数据范围，r*c最大约等于1000，于是不管三七二十一，先暴力枚举集合点再说。

2. 集合点确定，如何计算答案？

根据题意我们可以知道：

总路程=（n-1）个骑士到集合点的距离+有个骑士去接国王之间乱七八糟的距离

但是请注意，这里的距离并不是两点之间曼哈顿距离，而是通过日字形不断跳来跳去得到的。

那我们对于每一个点都进行BFS，看跳到集合点的最短路径是多少。 以上方法肯定是超时的，那我们又会用到一个常见技巧：在无向图中，起点到终点的最短路等于终点到起点的最短路。

于是我们从枚举的这个集合点开始跑BFS，这样就可以把所有点的最短路类似洪水填充似的都求出来啦。又由于枚举集合点不定，存储时候可用四维数组。

3.对于骑士接国王部分如何分析？

首先应该可以想到，骑士不可能总是刚好跳到国王那格子，若想最优国王大部分情况都会走一点距离的。。这也导致了不一定是最近的骑士去接国王。

但又很明显的是，骑士如果离国王越近，国王就可以走的越少，所以骑士跳到哪一格子最优也不知道。

于是就不会了

于是我们贪心地想，国王走的路应该不会超过骑士一次能超过的步数（2步），于是暴力枚举以国王为中心的5*5矩形确定接国王的点。

事实证明这样可以过，但是这个暴力翻遍题解也没有人详细证明，于是现在我们来hack他。

二.对于暴力枚举5*5矩形的hack

先上图：

RT,左下是亚瑟王，中间那个是圆桌骑士高文（雾）

红格子是我们构造出来的集合点，旁边的红圈是其他骑士，他们距离红格都只有1步，所以肯定选择那个点为集合点。

注意到此时高文已经不在王的5*5范围内了，我们来把两次距离算一算。

1. 我们来算一下现在的总距离

其他骑士总距离一共为5，高文到集合点距离为d（这样假设他离集合点很远也适用）

王到高文要走3步。所以一共为d+3+5=d+8步。

2.我们让高文走一步，分析5*5方格内情况。

我们注意到，当高文在王的对角线上时，最优可以缩短一步，于是王只用2步到高文。

然而高文往前走一步，最劣的情况是必须原路返回才能到集合点，于是高文回集合点需要d+2步。

其他骑士不变，共d+2+5+2=d+9步。

于是便hack了，骑士与王相遇点未必在5*5方格内。

3. 那是不是7*7方格就好了呢？

当然不是，由上可知，达到最劣情况满足以下条件均不能控制在某一方框内：

  1. 接王的骑士往内走一步会使到集合点的距离+1(就是原路返回的情况)
  2. 骑士处在王的对角线上

这里还要说说，可以想象出来，若不在对角线上则最优可以减少2步距离，那答案不变优也不会变劣。

4. 那这题是不是没做头了？

题当然还是可以做，你可以枚举棋盘上每一个点来判断是否为王与骑士相遇点，然后暴力枚举骑士，再暴力枚举集合点，最劣是O(R^3*C^3)，但是不可能达到这么大。

当然，本题最难的部分并不是这里，如果嫌麻烦也不用想太复杂，枚举5*5过了就算了吧。。

三.一些小细节

  1. 首先是读题。。行和列别搞混了。。

  2. 枚举5*5方格别越界都是小事了

  3. 洪水填充记忆化那里，应该入队时候就标记访问，不然在队列里时候还会增加一堆重复的。。

  4. 赋初值时小一点，我开了INT_MAX/3还爆了负数。。

四.丑陋的代码

不具有观赏性

//1. 枚举集合点O(10^3) //2. BFS算出各骑士到此点距离

//3. 再枚举集合点。。 //4. 枚举哪个骑士接（或都不接）国王最优。 //5. 总距离=其他骑士到点的距离+ //我到国王附近的距离+国王到附近的距离+国王附近到点距离；


#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

struct pp{
    int l,c;
    int d;
}kn[2000],ki;

int st,r,c;
int dx[8]={1,2,2,1,-1,-2,-2,-1};
int dy[8]={2,1,-1,-2,-2,-1,1,2};
bool v[50][30];
int ans=1000000000,sum,d[50][30][50][30];//d[a,b,c,d] -> (a,b) to (c,d)
queue<pp> q;

bool yuejie(int x,int y)
{
    return (x<=0||x>r||y<=0||y>c);
}

void bfs(int bx,int by)
{
    memset(v,0,sizeof(v));
    q.push((pp){bx,by,0}); v[bx][by]=1; d[bx][by][bx][by]=0;
    while (!q.empty())
    {

        int xx=q.front().l,yy=q.front().c;

        d[bx][by][xx][yy]=q.front().d; q.pop();

        for (int i=0;i<8;i++)
        {
            int x=xx+dx[i],y=yy+dy[i];
            if (!yuejie(x,y)&&!v[x][y]) v[x][y]=1,q.push((pp){x,y,d[bx][by][xx][yy]+1});
        }
    }
}

void print(int x,int y)
{
    for (int i=1;i<=r;i++,cout<<endl)
    for (int j=1;j<=c;j++) cout<<d[i][j][x][y]<<" ";
    cout<<endl;
}

int a(int x){return (x>0)?x:-x;}

int main()
{
    cin>>r>>c;
    memset(d,0x10f,sizeof(d));
    char cross; int line;
    while (cin>>cross>>line)
    {
        if (st==0) st=1,ki.l=line,ki.c=cross-'A'+1;
        else kn[st].l=line,kn[st++].c=cross-'A'+1;
    }
    st--;
    //1,2
    for (int i=1;i<=r;i++)
      for (int j=1;j<=c;j++) bfs(i,j);

    //3,4,5
    for (int i=1;i<=r;i++)
    for (int j=1;j<=c;j++)  //ji he point 
    {
        int sum=0;
//      print(i,j);
        for (int k=1;k<=st;k++) sum+=d[kn[k].l][kn[k].c][i][j];
        ans=min(sum+max(a(ki.l-i),a(ki.c-j)),ans);
        for (int k=1,summ=sum;k<=st;summ=sum,k++)  //knight who pick up the king
        {
            summ-=d[kn[k].l][kn[k].c][i][j];
            for (int ii=max(1,ki.l-3);ii<=min(r,ki.l+3);ii++)  //别越界了 
              for (int jj=max(1,ki.c-3);jj<=min(c,ki.c+3);jj++)
              ans=min(
                summ+d[kn[k].l][kn[k].c][ii][jj]+
                max(a(ii-ki.l),a(jj-ki.c))+d[ii][jj][i][j],ans);
        }
    }
    cout<<ans<<endl;
}