BISHI84　时津风的资源收集¶

中等通过率 50.43%python3样例通过牛客 AC广度优先搜索(BFS)

一句话

4 种资源都从 10 出发，求同时变到 (a,b,c,d) 的最少操作数。

解题思路¶

这题考什么¶

「看似 4 维状态空间，其实是 4 个一维问题」的拆分观察 + 一次 BFS 预处理。

关键点：每次操作只作用于单一资源，而合法性约束也只是「每种资源各自落在 [10, 300]」——四种资源之间毫无耦合。所以总操作数 = 各资源独立所需操作数之和，只要求出一张表 f[v] = 「单个资源从 10 变到 v 的最少步数」即可。

f 就是在 291 个点（10..300）上的无权最短路，用 BFS 从 10 出发跑一遍。每个点的出边：v±1、v±10、v±100（越界的丢掉）、以及两条「传送边」 v -> 300 和 v -> 10（对应「直接设为上限 / 下限」，任何位置都能一步到达）。

数据规模与复杂度¶

状态只有 291 个、每点 8 条边，BFS 是 O(291*8)，常数级； T <= 1e5 组询问，每组 O(1) 查表相加。若不预处理而对每组现搜，1e5 * BFS 必然 TLE。（反过来，如果真的把 (a,b,c,d) 当成 291^4 ≈ 7.2e9 的四维状态去 BFS，内存和时间都是天文数字——拆分观察是这题的全部。）

Python 的坑¶

BFS 队列用 collections.deque，虽然本题只有 291 个点，但保持习惯；list.pop(0) 在大图上是致命的；
T 可达 1e5，输出必须 "

".join 一次性 write，逐行 print 会被 IO 拖死；

「设为上限/下限」是从任意状态一步可达的边，别写成只有边界点才有—— 样例里 10 -> 300（1 步）正是靠这条边，300 才不用花 3 次 +100。

样例复核¶

f[10] = 0；f[100] = 2（+100 到 110，再 -10）； f[200] = 2（设为 300，再 -100）；f[300] = 1（设为上限）。合计 0 + 2 + 2 + 1 = 5，与样例一致。

参考实现¶

solutions/BISHI84.py
import sys
from collections import deque

LO, HI = 10, 300


def build_table():
    """f[v] = 单个资源从 10 出发变到 v 的最少操作次数。"""
    f = [-1] * (HI + 1)
    f[LO] = 0                # 起点是 10，走 0 步
    q = deque([LO])          # 边权全为 1，BFS 的出队顺序就是步数递增顺序
    while q:
        v = q.popleft()
        d = f[v] + 1
        # 六条增减边 + 两条「设为上限/下限」的传送边，任何位置都能一步到 HI 或 LO
        for u in (v - 1, v + 1, v - 10, v + 10, v - 100, v + 100, HI, LO):
            if LO <= u <= HI and f[u] < 0:   # 越界丢弃；f[u] < 0 即尚未访问
                f[u] = d                     # 首次访问即最短，之后不再更新
                q.append(u)
    return f


def main() -> None:
    f = build_table()                            # 全部询问共用这一张表
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    idx = 1                                      # data[0] 是组数，数据从下标 1 开始
    # 每组四个数，游标一次推进 4，全程只查表不再搜索
    for _ in range(t):
        a = int(data[idx]); b = int(data[idx + 1])
        c = int(data[idx + 2]); d = int(data[idx + 3])
        idx += 4
        out.append(str(f[a] + f[b] + f[c] + f[d]))   # 四种资源互相独立，直接求和
    sys.stdout.write("\n".join(out) + "\n")


main()

BISHI84 时津风的资源收集¶