[USACO09OCT] Invasion of the Milkweed G

GitHub跳转原题关系图返回列表

从初始格做八方向 BFS，最远可达草地的距离就是完全侵占周数。

OJ: luogu

题目 ID: P2960

难度:普及-

标签:BFS网格dequepython

日期: 2026-07-16 20:10

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

乳草每周向周围八格的非岩石地扩散，求占领最后一块草地的时间。

思路

每次扩散代价都是一周，多源波次实际只有一个初始格，因此普通 BFS 求出的格子距离就是首次被占领时间，答案为最大距离。

输入地图从上到下，而起点坐标以左下为原点，所以起始行要转换为 height - start_y。

Python 知识

  • deque 做 BFS 队列。
  • 字典 distance 同时判重和保存周数。
  • 两层 for dr/dc in (-1,0,1) 简洁枚举八邻域；原格因已访问会自动跳过。

代码

python
import sys
from collections import deque


input = sys.stdin.buffer.readline
width, height, start_x, start_y = map(int, input().split())
field = [input().strip() for _ in range(height)]
start = (height - start_y, start_x - 1)
queue = deque([start])
distance = {start: 0}

while queue:
    row, column = queue.popleft()
    for dr in (-1, 0, 1):
        for dc in (-1, 0, 1):
            neighbor = row + dr, column + dc
            if (neighbor not in distance and 0 <= neighbor[0] < height
                    and 0 <= neighbor[1] < width and field[neighbor[0]][neighbor[1]] == 46):
                distance[neighbor] = distance[(row, column)] + 1
                queue.append(neighbor)
print(max(distance.values()))

复杂度

每格至多访问一次，时间和空间均为 O(XY)O(XY)。

总结

“同步每周扩散”就是无权图最短距离波次，最后完成时间等于最远点距离。