题解 P1930 【[USACO3.3]亚瑟王的宫殿】

· · 题解

（〇）写在前面的话

在此之前，该题已经有很多题解，但它们大多是枚举国王周围5\times 5的范围（玄学贪心？），最后计算最小距离。

虽然能AC，但其实这种做法是不严谨的( 详见巨佬的hack数据 )

然而将5\times 5的范围扩大至R\times C的范围后，时间复杂度过大。那么，这道题真的无解了吗？

蒟蒻的我用spfa在正确的结果和正确的时间复杂度内AC了此题(而且过了hack数据)。

（一）解题思路

题目不再阐述。题目传送门

这道题求的是所有骑士以及国王到某集合点的最小距离(任意骑士与国王汇合后，可以带着国王一起走，并且只算一个人的距离)。

Step1：关于集合点

集合点是哪一个？不知道。不知道就枚举

与其它题解无异，看到范围十分小的R、C后，毅然选择枚举集合点。

枚举后，相当于已经知道了集合点，求骑士和国王从原所在地到该点的最小距离和。

这个可以反过来看，也就是从集合点出发，求出骑士和国王从集合点到骑士和国王原所在地的距离的最小值。

显然，上述两者是等价的。因此，我们可以用最短路算法直接求出最小的距离之和。这里使用spfa。

Step2：关于最短路

定义dis(x, y, 0)表示集合点到点(x,y)的最小距离(最少步数，不带国王)。

定义dis(x, y, 1)表示集合点到点(x,y)的最小距离(最少步数，此时在点(x,y)，骑士已经带上了(或者是正在带着)国王）

考虑如何转移。

显然，对于dis(x,y,0)这个状态，可以作两种转移:

  1. 当前骑士没有带国王

可以转移出8个状态(即骑士走的八个"日"字)，设转移后的状态为dis(x', y', 0)。因为骑士转移到这个状态只需要一步，所以边权为1。

转移方程为dis(x', y', 0) =\min\{dis(x, y, 0) +1\}

  1. 当前骑士带上了国王

可以转移出一个状态，设国王走到(x,y)需要的步数为val。转移后的状态为dis(x,y,1)。

转移方程为dis(x,y,1)=\min\{dis(x,y,0)+val\}

同样，dis(x,y,1)也可以是从其他的dis(x',y',1)转移过来。转移方程很简单。

Step3：结果的处理

spfa跑完后，我们得到了dis(x,y,z)数组，但题目要求的是距离和的最小值。

简单，将最小值累加即可。等等，那么问题来了，哪位骑士带国王???

也就是说，我们需要找到一个骑士，累加他的dis(x,y,1)，同时累加其它骑士的dis(x,y,0)，使得总和最小。

容易证明，dis(x,y,0)\leq dis(x,y,1)

因此，我们只需要枚举每个(x,y)，求出\min\{dis(x,y,1)-dis(x,y,0)\}，然后加上所有dis(x,y,0)即可。

最差时间复杂的\Theta (R^2C^2)时间都花在枚举上了，稳稳地过，不需要卡常。

（二）代码

我知道大家喜欢看这个

有注释哦。

#include<bits/stdc++.h>
using namespace std;
const int maxr = 45, maxc = 30, INF = 1e6 + 7;
int R, C, Map[maxr][maxc], Kingx, Kingy;
int X[8] = {-1, 1, 2, 2, 1, -1, -2, -2}, Y[8] = {2, 2, 1, -1, -2, -2, -1, 1};
struct node{
    int x, y;
    bool king;//记录是否带国王
};
queue< node > q;
int Abs(int x){//求绝对值 
    if(x < 0) return -x;
    if(x == 0) return 0;
    if(x > 0) return x;
}
int spfa(int x,int y){
    int dis[maxr][maxc][2] = {}; bool vis[maxr][maxc][2] = {};//初始化dis，vis数组(spfa常规操作) 
    for(int i=1; i<=R; i++)//初始化dis数组，同样是常规操作 
        for(int j=1; j<=C; j++)
            dis[i][j][0] = dis[i][j][1] = INF;
    node t;
    if(x == Kingx and y == Kingy) dis[x][y][1] = 0, t.king = true;//如果集合点的位置是国王的位置(不用考虑国王的移动)，初始状态就是dis[x][y][1] 
    else dis[x][y][0] = 0, t.king = false;//如果集合点的位置不是国王的位置，需要考虑国王的移动，初始状态是dis[x][y][0]
    t.x = x, t.y = y;
    q.push(t);//入队，常规操作 
    vis[x][y][t.king] = true;//标记,常规操作 
    while(!q.empty()){//一下均为spfa常规操作
        int dx = q.front().x, dy = q.front().y;
        bool flag = q.front().king;
        q.pop();
        for(int i=0; i<8; i++){//不进行带国王的操作 
            int ex = dx + X[i], ey = dy + Y[i];
            if(ex < 1 or ey < 1 or ex > R or ey > C) continue;
            if(dis[ex][ey][flag] > dis[dx][dy][flag] + 1){
                dis[ex][ey][flag] = dis[dx][dy][flag] + 1;
                if(!vis[ex][ey][flag]){
                    vis[ex][ey][flag] = true;
                    node e; e.x = ex, e.y = ey, e.king = flag;
                    q.push(e);
                }
            }
        }
        if(!flag){//在(dx, dy)这个点带上国王(让国王自己走到这个点) 
            int val = dis[dx][dy][flag] + max(Abs(dx-Kingx), Abs(dy-Kingy));
            //算出国王走到这个点的步数,国王可以走八个方向，不是曼哈顿距离，而是max(Abs(dx-Kingx), Abs(dy-Kingy),自行画图理解 
            if(dis[dx][dy][!flag] > val){
                dis[dx][dy][!flag] = val;
                if(!vis[dx][dy][!flag]){
                    vis[dx][dy][!flag] = true;
                    node e; e.x = dx, e.y = dy, e.king = !flag;
                    q.push(e);
                }
            }
        }
        vis[dx][dy][flag] = false;
    }
    int minu = INF, cnt = 0;//最短路跑完后，算出最短的总距离
    //容易证明，骑士所在的点的状态dis[x][y][1]>=dis[x][y][0]，要使总距离最小，只需要找最小的(dis[x][y][1]-dis[x][y][0])，最后加上所有骑士的距离dis[x][y][0]即可 
    for(int i=1; i<=R; i++)
        for(int j=1; j<=C; j++)
            if(Map[i][j] == 1) minu = min(minu, dis[i][j][1] - dis[i][j][0]), cnt += dis[i][j][0];
    return cnt+minu;
}
int main(){
    cin>>C>>R;//写到最后发现R,C打反了，不想改了，将就着看吧 
    char kingx;
    cin>>kingx>>Kingy;//读入 
    Kingx = kingx-'A'+1;//Kingx储存国王的横坐标，Kingy储存国王的纵坐标 
    char knightx; int knighty;
    while(cin>>knightx>>knighty){//读入 
        Map[knightx-'A'+1][knighty] = 1;//邻接矩阵标记国王的位置 
    }
    int ans = INF;//初始化 
    for(int i=1; i<=R; i++) 
        for(int j=1; j<=C; j++)
            ans = min(ans, spfa(i, j));//枚举集合点，spfa求最短距离 
    if(ans == INF) printf("0");
    else printf("%d", ans);
    return 0;
}