八连通网格上从起点做 BFS 求最晚被占领格子的层数，起点算第 0 周，答案即所有格子距离的最大值。
OJ: roj
题目 ID: 3081
难度:普及-
标签:搜索广度优先搜索BFS
创建: 2026-10-01 15:14
更新: 2026-10-07 13:50
前置题目
roj 1335【例2-4】连通块B 的八连通 BFS 直接用 A 教的「扩展条件里一次挡掉越界与障碍、入队即标记」这一网格搜索骨架（B 代码同样先判 in_map 再把 dist 置为 week+1 后 append），A 还点明八连通只需扩 DIRS；B 只把栈换成队列并叠加层数记录与取全图最大值，得到最晚占领周数。roj 1255迷宫问题B 直接复用 A 教的网格 BFS 中首次入队即最短步数这一层数判定，只把四连通换成八连通并把单点到点距离改为全图最大层数roj 1329【例8.2】细胞B 的八连通 BFS 直接复用 A 教的「入队即标记、每格至多入队一次」这一 BFS 不变式来替代逐周全图重扫，只在其上叠加八方向扩散与取最大层数作为答案，属同为 BFS 模板但强度提升一级的台阶关系。
题目描述
. 为草地、* 为大石。乳草第 4 3 1 1 / .... ..*. .**.，输出 4。
思路
从起点做八连通 BFS，每个格子被占领的星期数就是它到起点的最短路层数（起点为第
参考代码
Python 版：
python
#!/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 15:14
# update_at: 2026-10-01 15:14
from collections import deque
# 八个方向的位移：水平、垂直加上四条对角线
DELTA = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
def solve() -> None:
it = iter(map(int, input().split()))
x, y, mx, my = next(it), next(it), next(it), next(it)
# 地图按输入顺序存第 y 行，grid[ny-1] 对应坐标里的第 ny 行
grid = [input().rstrip() for _ in range(y)]
# dist 记录每个格子的占领星期数，未访问为 -1；石头永不入队
dist = [[-1] * x for _ in range(y)]
def spread(queue: deque) -> None:
"""BFS 一层一层扩散，队头出队的星期数就是该格被占领的最早时间。"""
while queue:
ny, nx, week = queue.popleft()
for dy, dx in DELTA:
fy, fx = ny + dy, nx + dx
in_map = 0 <= fy < y and 0 <= fx < x
if in_map and grid[fy][fx] == "." and dist[fy][fx] == -1:
dist[fy][fx] = week + 1
queue.append((fy, fx, week + 1))
dist[my - 1][mx - 1] = 0
spread(deque([(my - 1, mx - 1, 0)]))
# 石头的 -1 不影响最大值，答案就是所有格子的最晚占领时间
print(max(max(row) for row in dist))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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 11:40
* update_at: 2026-10-06 11:40
*/
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int MAXX = 105;
const int MAXY = 105;
// 八个方向：水平、垂直以及四条对角线
const int DX[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int DY[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
ll X, Y, Mx, My;
char grid[MAXY][MAXX]; // grid[y][x] 存第 y 行第 x 列的字符，'.' 为草地，'*' 为石头
ll dist[MAXY][MAXX]; // dist[y][x] 为格子 (x, y) 被占领的星期数，-1 表示未访问
// 队列节点：格子坐标，对应数组下标
struct Node {
ll x;
ll y;
};
queue<Node> q;
int main() {
cin >> X >> Y >> Mx >> My;
for (ll y = 1; y <= Y; y++) {
for (ll x = 1; x <= X; x++) {
cin >> grid[y][x];
dist[y][x] = -1;
}
}
// 起点在第 0 周就被占领，从它开始逐层 BFS 扩散
dist[My][Mx] = 0;
Node start;
start.x = Mx;
start.y = My;
q.push(start);
while (!q.empty()) {
Node now = q.front();
q.pop();
for (int d = 0; d < 8; d++) {
ll nx = now.x + DX[d];
ll ny = now.y + DY[d];
if (nx < 1 || nx > X || ny < 1 || ny > Y) {
continue;
}
if (grid[ny][nx] == '*' || dist[ny][nx] != -1) {
continue;
}
dist[ny][nx] = dist[now.y][now.x] + 1;
Node nxt;
nxt.x = nx;
nxt.y = ny;
q.push(nxt);
}
}
// 答案是最晚被占领格子的星期数，石头的 -1 不影响取最大值
ll answer = 0;
for (ll y = 1; y <= Y; y++) {
for (ll x = 1; x <= X; x++) {
if (dist[y][x] > answer) {
answer = dist[y][x];
}
}
}
cout << answer << endl;
return 0;
}