usaco-3.3.3 亚瑟王的宫殿

形式化题目

在一个 $R$ 行 $C$ 列的棋盘上（ $1 \leqslant R \leqslant 40$ ， $1 \leqslant C \leqslant 26$ ）放着一枚国王和若干枚骑士，任意两枚棋子不在同一格。

国王一步可以走到八邻域中的任意一格；记国王从格 $u$ 走到格 $v$ 的最少步数为 $K(u,v)$ ，它就是两个方向偏移量的较大者（切比雪夫距离）。
骑士一步走"日"字（8 个方向）；记骑士从 $u$ 到 $v$ 的最少步数为 $D(u,v)$ ，不存在则记 $+\infty$ 。
有一枚骑士可以先去接国王：它先走到某个格 $u$ ，国王自己走到 $u$ （花 $K(\text{king},u)$ 步），此后两者合为一体，一起从 $u$ 走到 $t$ （花 $D(u,t)$ 步）；国王与骑士同行时不再单独计步，而且整个方案里至多只有一枚骑士这样做。
其余骑士各自独立地从自己的起点走到 $t$ 。

要求选一个格 $t$ 作集合点，使总步数最小：

\min_t \Bigl(\ \sum_{k} D(k,t)\ +\ \min\Bigl(K(\text{king},t),\ \min_k \min_u \bigl[D(k,u)+K(\text{king},u)+D(u,t)-D(k,t)\bigr]\Bigr)\Bigr)

上面括号中第一项是"国王自己走到 $t$ "，第二项是"由第 $k$ 枚骑士在 $u$ 接上国王"，它对 $k,u$ 取最小。下文的"形式化"到这里为止，具体求法在正文推导。

正解

思路

先只看骑士

如果棋盘上没有国王，答案就很直白：固定集合点 $t$ 后，每枚骑士各走各的，

\mathrm{cost}(t)=\sum_{k} D(k,t)

于是做 $k$ 次 BFS 得到每枚骑士到所有格子的距离（这一份距离表后面还要反复用），再对全部 $R\times C$ 个格子取最小即可。这一步是后面全部讨论的基础。

国王带来三种方案

国王的存在把问题拆成三种互斥的情形：

国王单独行动：它自己走到 $t$ ，代价 $K(\text{king},t)$ ，与骑士们互不影响，总代价就是 $\mathrm{cost}(t)+K(\text{king},t)$ 。
某枚骑士携带国王：第 $k$ 枚骑士先绕到 $u$ 接上国王，再一起到 $t$ ，总代价
$\mathrm{cost}(t)+\bigl[D(k,u)+K(\text{king},u)+D(u,t)-D(k,t)\bigr]$
方括号里减去的 $D(k,t)$ 是"这枚骑士本来也要从自己起点走到 $t$ "的那段，它已经在 $\mathrm{cost}(t)$ 里算过，所以这里只补差值。
（不合法）多枚骑士接力护送国王：题面规定同行只算一枚骑士，所以不会出现这种方案。

情况 1 的代价是现成的，麻烦在情况 2：如果直接对 $(k,u,t)$ 三重枚举，就是 $O(k\cdot n^2)$ ，其中 $n=R\times C$ ， $k$ 多达 781、 $n$ 多达 1040，会 TLE。

把 $(k,u)$ 这一层用一次最短路合并掉

固定骑士 $k$ 、固定集合点 $t$ 后，方括号里要最小化的是 $u$ ：

E_k(t)\ \overset{\text{def}}{=}\ \min_u \bigl[D(k,u)+K(\text{king},u)+D(u,t)\bigr]

把 $D(k,u)+K(\text{king},u)$ 看成"骑士 $k$ 绕到 $u$ 接国王"的固定开销，它就是 $t=u$ 时的答案，也就是距离场 $E_k$ 的初始种子：

E_k(u)\ \leftarrow\ D(k,u)+K(\text{king},u)

剩下的 $+D(u,t)$ 正是"在骑士图上从 $u$ 走到 $t$ "，所以整个 $E_k$ 就是：以这批种子为初值，在骑士图上做一次多源最短路（每走一步加 1）。国王那张棋盘距离表 $K(\text{king},\cdot)$ 只依赖国王的初始位置，题目里只有一枚国王，所以它只需要算一次，全部骑士共用。

这一步把 $O(n^2)$ 的"每个 $t$ 都重新枚举 $u$ "降到一次 $O(n)$ 的多源最短路，于是每枚骑士的总代价变成两趟 $O(n)$ ：

距离场	种子	传播方式	含义
$D(k,\cdot)$	$D(k,k)=0$	单源 BFS	骑士 $k$ 自己从起点出发到各格
$E_k(\cdot)$	$D(k,u)+K(\text{king},u)$	多源最短路（同一张图）	骑士 $k$ 绕去 $u$ 接国王后再到各格

多源最短路本来要堆优化 Dijkstra，但这里每条边权都是 1，而种子值的最大值 $\max_u\bigl(D(k,u)+K(\text{king},u)\bigr)$ 就是距离的上界，量级只有 $O(n)$ 。因此可以开一排"桶"按距离值分层，从桶 $0$ 一路扫到桶上界，等价于 Dial 算法，省掉堆的 $O(\log n)$ 因子。

合并答案

记

\mathrm{gain}(t)=\min_k\bigl[E_k(t)-D(k,t)\bigr]

它就是"挑一枚骑士去接送国王、相对让它自己走"的最小增量。于是集合点 $t$ 的答案

\mathrm{cost}(t)+\min\bigl(K(\text{king},t),\ \mathrm{gain}(t)\bigr)

对全部 $t$ 取最小就是最终答案。注意 $\mathrm{gain}(t)$ 与 $K(\text{king},t)$ 都要参与取 $\min$ （而不是只取 $\mathrm{gain}$ ）：国王自己走过去可能更便宜，样例里就出现过两种方案打平的情况。

样例走一遍

样例是 $8\times8$ 棋盘，国王在 D4，骑士在 A3、A8、H1、H8。棋盘与最优路线（集合点 B5）如下：

text

1
2
3
4
5
6
7
8
9
10     A  B  C  D  E  F  G  H
 8   N2  .  .  .  .  .  .  N4
 7   .   .  .  .  .  .  .   .
 6   .   .  .  .  .  .  .   .
 5   .   *   .  .  .  .  .   .        * = 集合点 B5，K = 国王 D4
 4   .   .  .  K  .  .  .   .        N1 = A3   N2 = A8
 3   N1  .  .  ^  .  .  .   .        N3 = H1   N4 = H8
 2   .   .  .  |  .  .  .   .
 1   .   .  .  |  .  .  N3  .
               H1 的路线：H1 -> G3 -> F5 -> D4(接国王) -> B5

四枚骑士各自到 B5 的距离是 $D(\mathrm{A3},\mathrm{B5})=1$ 、 $D(\mathrm{A8},\mathrm{B5})=2$ 、 $D(\mathrm{H1},\mathrm{B5})=4$ 、 $D(\mathrm{H8},\mathrm{B5})=3$ ，和正好是 $\mathrm{cost}(\mathrm{B5})=10$ ，与题面提示完全一致。值得注意的是 H1 那枚骑士本来走到 B5 就要 4 步，而它顺路经过 D4（ $D(\mathrm{H1},\mathrm{D4})=3$ ），在那里把国王捎上完全不绕路——所以 $\mathrm{gain}(\mathrm{B5})=E_{\mathrm{H1}}(\mathrm{B5})-D(\mathrm{H1},\mathrm{B5})=4-4=0$ ，国王"搭便车"的增量是 0。

再对比附近几个候选点，就能看出两个 $\min$ 分支都不能省：

集合点 $t$	$\mathrm{cost}(t)=\sum_k D(k,t)$	国王自己走 $K(\text{king},t)$	最佳携带增量 $\mathrm{gain}(t)$	总代价
B5	10	2	0（骑士 H1 顺路经过 D4）	10 ✅
C4	10	1	1	11
E5	10	1	1	11
D6	10	2	1	11
E2	12	2	0	12

C4 与 E5 的 $\mathrm{cost}$ 和 B5 一样是 10，国王自己走过去还更快（1 步），但携带方案要多绕 1 步，两相权衡后 B5 以 10 胜出——这正是"分别取两种方案的最小值"带来的结果。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 05:39
# update_at: 2026-10-01 05:39

import sys
from collections import deque

# 骑士的 8 种走法：(列偏移, 行偏移)，即"日"字形的八个方向
KNIGHT_STEPS = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2))
INF = 10**9  # 不可达哨兵：只参与取最小值，不会与真实步数混淆


def knight_dist(src: int, moves: tuple[tuple[int, ...], ...]) -> list[int]:
    """骑士从 src 出发到每个格子的最少步数，到不了记 -1。"""
    dist = [-1] * len(moves)
    dist[src] = 0
    queue = deque([src])
    while queue:
        u = queue.popleft()
        step = dist[u] + 1
        for v in moves[u]:
            if dist[v] < 0:  # 边长全为 1，第一次到达就是最短路
                dist[v] = step
                queue.append(v)
    return dist


def carry_min(dist: list[int], walk: list[int], moves: tuple[tuple[int, ...], ...]) -> list[int]:
    """E[t] = min_u (D_k(u) + walk(u) + D(u,t))：这名骑士绕到 u 接国王、再赶到 t 的代价。

    国王自己走到 u 要 walk(u) 步，所以种子取 E[u] = D_k(u) + walk(u)；
    再沿骑士图做一次多源 BFS。种子最大值就是值域上界，用桶（Dial 队列）代替堆。
    """
    limit = max(d + w for d, w in zip(dist, walk) if d >= 0)
    best = [INF] * len(moves)
    buckets = [[] for _ in range(limit + 1)]
    for u, (d, w) in enumerate(zip(dist, walk)):
        if d >= 0 and d + w < best[u]:
            best[u] = d + w
            buckets[d + w].append(u)
    for d in range(limit + 1):
        for u in buckets[d]:
            if best[u] < d:  # 这个格子已被更小的种子值刷新，桶里的副本作废
                continue
            for v in moves[u]:
                if d + 1 < best[v]:
                    best[v] = d + 1
                    buckets[d + 1].append(v)
    return best


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    rows, cols = int(next(data)), int(next(data))
    king_col, king_row = next(data)[0] - 65, int(next(data)) - 1
    # 之后每两个 token 是一个骑士：列字母 + 行号
    knight_ids = [(int(r) - 1) * cols + (c[0] - 65) for c, r in zip(data, data)]

    n = rows * cols
    moves = tuple(  # 先把棋盘外剔除，BFS 时不用再判边界
        tuple((r + dr) * cols + (c + dc) for dc, dr in KNIGHT_STEPS
              if 0 <= c + dc < cols and 0 <= r + dr < rows)
        for r in range(rows) for c in range(cols)
    )
    # 国王单独走到某格所需步数（切比雪夫距离），只需要算一次
    walk = [max(abs(c - king_col), abs(r - king_row)) for r in range(rows) for c in range(cols)]

    base = [0] * n      # base[t]：所有骑士各自直奔 t 的步数和
    gain = [INF] * n    # gain[t]：min over k of (E_k[t] - D_k(t))，携带国王带来的增量
    reach = [0] * n     # reach[t]：能走到 t 的骑士数，等于骑士总数才能当集合点
    for k in knight_ids:
        dist = knight_dist(k, moves)
        carry = carry_min(dist, walk, moves)
        for t, d in enumerate(dist):
            if d < 0:
                continue
            base[t] += d
            reach[t] += 1
            delta = carry[t] - d
            if delta < gain[t]:
                gain[t] = delta

    # 集合点 t 的代价：国王自己走过去 walk[t]，或由某名骑士接送（gain[t]），取较小者
    print(min(
        base[t] + min(walk[t], gain[t])
        for t in range(n)
        if reach[t] == len(knight_ids)
    ))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:01
 * update_at: 2026-10-06 10:01
 */
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

typedef long long ll;

const int MAXN = 40 * 26 + 5;  // 棋盘最多 40 行 26 列，格子总数上界
const ll INF = 1e9;            // 不可达哨兵：只参与取最小值

// 骑士的 8 种走法：(行偏移, 列偏移)，即"日"字形的八个方向
const int DR[8] = {1, 2, 2, 1, -1, -2, -2, -1};
const int DC[8] = {2, 1, -1, -2, -2, -1, 1, 2};

ll R, C, n;           // 行数、列数、格子总数
ll kingCol, kingRow;  // 国王的列（0 起）、行（0 起）
ll knightCnt;         // 骑士数量
ll knightId[MAXN];    // knightId[i] = 第 i 枚骑士起点的一维编号

std::vector<ll> adj[MAXN];  // 骑士图邻接表：建表时就把越界方向剔除
ll walk[MAXN];              // walk[u] = 国王从起点走到 u 的步数（切比雪夫距离），只算一次
ll dist[MAXN];              // 骑士 BFS 距离数组，-1 表示不可达
ll best[MAXN];              // 携带距离场 E_k 的当前最优值
ll base[MAXN];              // base[t] = 所有骑士各自直奔 t 的步数和
ll gain[MAXN];              // gain[t] = min_k (E_k(t) - D_k(t))，派骑士接国王的增量
ll reach[MAXN];             // reach[t] = 能走到 t 的骑士数，等于总数才可作集合点
std::vector<ll> bucket[MAXN * 2];  // Dial 桶：bucket[d] 存当前最优值为 d 的格子

// 计算国王走到每个格子的步数：八邻域每步一格，即两个方向偏移量的较大者
void calc_walk() {
    for (ll r = 0; r < R; ++r)
        for (ll c = 0; c < C; ++c) {
            ll dr = r > kingRow ? r - kingRow : kingRow - r;
            ll dc = c > kingCol ? c - kingCol : kingCol - c;
            walk[r * C + c] = dr > dc ? dr : dc;
        }
}

// 骑士从 src 出发到每个格子的最少步数，到不了记 -1。
// 骑士图边权全为 1，普通 BFS 第一次到达就是最短路。
void bfs_knight(ll src) {
    memset(dist, -1, sizeof(ll) * n);
    std::queue<ll> q;
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
        ll u = q.front(); q.pop();
        for (ll i = 0; i < (ll)adj[u].size(); ++i) {
            ll v = adj[u][i];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

// E[t] = min_u (D_k(u) + walk(u) + D(u,t))：这枚骑士绕到 u 接上国王、再赶到 t 的代价。
// 种子取 E[u] = D_k(u) + walk(u)（u 即接人点），再沿骑士图做多源 BFS。
// 种子值就是距离上界（量级 O(n)），用桶按距离值分层扫描，省掉堆。
// 注意：本次调用的前提是 dist[] 里已经是这枚骑士的单源距离场。
void bfs_carry() {
    ll limit = 0;  // 桶的层数上界 = 种子最大值
    for (ll u = 0; u < n; ++u)
        if (dist[u] != -1 && dist[u] + walk[u] > limit)
            limit = dist[u] + walk[u];

    for (ll d = 0; d <= limit; ++d) bucket[d].clear();
    for (ll u = 0; u < n; ++u) {
        if (dist[u] == -1) continue;   // 骑士到不了 u，接人方案不成立
        best[u] = dist[u] + walk[u];   // 种子：骑士先到 u，国王自己走到 u
        bucket[best[u]].push_back(u);
    }

    // 从桶 0 到桶 limit 逐层向外松弛，等价于边权为 1 的多源最短路
    for (ll d = 0; d <= limit; ++d)
        for (ll i = 0; i < (ll)bucket[d].size(); ++i) {
            ll u = bucket[d][i];
            if (best[u] < d) continue;  // 该格已被更小的种子值刷新，桶里副本作废
            for (ll j = 0; j < (ll)adj[u].size(); ++j) {
                ll v = adj[u][j];
                if (d + 1 < best[v]) {
                    best[v] = d + 1;
                    bucket[d + 1].push_back(v);
                }
            }
        }
}

int main() {
    // 输入：第一行 R C；之后每两个 token 是"列字母 行号"，第一个是国王，其余是骑士
    if (scanf("%lld %lld", &R, &C) != 2) return 0;
    char colCh;
    ll row;
    scanf(" %c %lld", &colCh, &row);
    kingCol = colCh - 'A';
    kingRow = row - 1;
    knightCnt = 0;
    while (scanf(" %c %lld", &colCh, &row) == 2)
        knightId[knightCnt++] = (row - 1) * C + (colCh - 'A');

    n = R * C;

    // 骑士图邻接表：把棋盘外的走法在建表时剔除，BFS 时不用再判边界
    for (ll r = 0; r < R; ++r)
        for (ll c = 0; c < C; ++c) {
            ll u = r * C + c;
            for (ll d = 0; d < 8; ++d) {
                ll nr = r + DR[d], nc = c + DC[d];
                if (nr >= 0 && nr < R && nc >= 0 && nc < C)
                    adj[u].push_back(nr * C + nc);
            }
        }

    calc_walk();

    for (ll t = 0; t < n; ++t) {
        base[t] = 0;
        gain[t] = INF;   // 还没有任何携带方案时，增量记为不可达
        reach[t] = 0;
    }

    // 每枚骑士：一趟单源 BFS 求 D_k(·)，一趟桶式多源 BFS 求携带场 E_k(·)
    for (ll k = 0; k < knightCnt; ++k) {
        bfs_knight(knightId[k]);
        bfs_carry();
        for (ll t = 0; t < n; ++t) {
            if (dist[t] == -1) continue;  // 这枚骑士到不了 t
            base[t] += dist[t];
            reach[t]++;
            if (best[t] - dist[t] < gain[t])
                gain[t] = best[t] - dist[t];
        }
    }

    // 集合点 t 的代价 = cost(t) + min(国王自己走 walk[t], 携带增量 gain[t])
    // 两个分支都要取 min：国王自己走过去可能更便宜
    ll ans = INF;
    for (ll t = 0; t < n; ++t) {
        if (reach[t] != knightCnt) continue;  // 必须所有骑士都能到
        ll extra = walk[t] < gain[t] ? walk[t] : gain[t];
        if (base[t] + extra < ans)
            ans = base[t] + extra;
    }
    printf("%lld\n", ans);
    return 0;
}

几个实现要点：

坐标压成一维。输入是"列字母 + 行号"，先统一成 $id=(\text{row}-1)\times C+(\text{col}-\text{A})$ ，之后所有距离都是 list[int] 下标，避免在热循环里做二维坐标运算。
骑士图预处理成邻接表 moves：建表时就把越界方向剔除，BFS 里不必再判边界。
不可达用 $-1$ （BFS）和 INF = 10**9（携带距离场）两种哨兵：前者要参与"是否所有骑士都能到达"的判定，后者只参与取最小值。reach[t] 统计能走到 $t$ 的骑士数，只有等于骑士总数时 $t$ 才是合法集合点；棋盘只有 $1\times1$ 之类极小的情形，正是靠这一条自然处理（此时只有 0 枚骑士，全部格子都满足条件，答案为 0）。
carry_min 的一个易错点：同一个格子 $u$ 可能以多个种子值被压进不同的桶，扫描到旧的桶项时要跳过已被刷新的格子（if best[u] < d: continue），否则会用更大的值继续往外传播。

复杂度

设 $n=R\times C$ 为格子数、 $k$ 为骑士数。每枚骑士做一次单源 BFS 和一次多源最短路，都是 $O(n)$ ，所以

时间复杂度： $O(k\cdot n)$ 。本题 $k\leqslant n\leqslant 40\times26=1040$ ，最坏约 $10^6$ 量级的边松弛。
空间复杂度： $O(n+k)$ ，主要是骑士图的邻接表和几个长度 $n$ 的距离数组（骑士图邻接表 $O(8n)$ ）。

总结

先固定集合点 $t$ ，形式化出 $\sum_k D(k,t)$ ，再用 $k$ 次 BFS 得到全部 $D(k,\cdot)$ 。
国王只有两种独立处理方式：自己走到 $t$ （切比雪夫距离），或被某枚骑士携带。携带的代价是 $D(k,u)+K(\text{king},u)+D(u,t)$ ，要减去重复计算的 $D(k,t)$ 。
关键优化是把"枚举接送点 $u$ "折叠进一次多源最短路：种子取 $D(k,u)+K(\text{king},u)$ ，答案就是 $E_k(t)$ ，把 $O(k\cdot n^2)$ 降成 $O(k\cdot n)$ 。
边权全为 1 时用桶（Dial）代替堆；国王的棋盘距离表只算一次、全骑士共用。
最后对每个 $t$ 取 $\min\bigl(K(\text{king},t),\ \mathrm{gain}(t)\bigr)$ ，两种方案都不能省。