把黑砖看成网格图的顶点，答案是起点所在连通分量的大小；一次洪水填充 O(WH) 求出。
OJ: roj
题目 ID: 1216
难度:普及-
标签:搜索深度优先搜索广度优先搜索网格连通性python
创建: 2026-09-30 00:01
更新: 2026-10-05 05:42
题目描述
多组数据，读到 0 0 结束：每组给出 . 是黑砖、# 是红砖、@ 是黑砖且是你所站的位置。只能上下左右移动到相邻黑砖，求能到达的黑砖数（含起点）。
样例输入：第一行 6 9，随后 9 行依次是 ....#.、.....#、......、......、......、......、......、#@...#、.#..#.，最后一行 0 0。样例输出：45。
思路
黑砖是顶点、四方向相邻是边、红砖不进图，答案就是起点所在连通分量的大小，与走的路线无关。从 @ 出发做一次洪水填充，每块黑砖入栈时就染色成红砖，保证每个格子只被计数一次。
参考代码
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-09-30 00:01
# update_at: 2026-09-30 00:01
import sys
BLACK = '.' # 可走的黑色瓷砖
START = '@' # 黑色瓷砖，且是出发点
DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1)) # 上、下、左、右四个相邻方向
TILES = frozenset('.#@') # 瓷砖字符；用它把数字流和网格字符流分开
def count_reachable(grid: list[str], h: int, w: int, start: tuple[int, int]) -> int:
"""从 start 出发能到达的黑砖数（含起点）：一次洪水填充，走过的格子染色不再回访。"""
board = [list(row) for row in grid] # 就地染色需要可变副本
board[start[0]][start[1]] = '#' # 起点即已访问
stack = [start]
count = 0
while stack:
r, c = stack.pop()
count += 1
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
# 先判在界内，短路顺序保证越界时不会读数组
if 0 <= nr < h and 0 <= nc < w and board[nr][nc] == BLACK:
board[nr][nc] = '#' # 入栈即标记，同一点不会被重复压栈
stack.append((nr, nc))
return count
def solve() -> None:
text = sys.stdin.buffer.read().decode()
sizes = iter(int(token) for token in text.split() if token.isdigit()) # 只有 W、H 是数字
tiles = [ch for ch in text if ch in TILES] # 网格字符跨行连续，按原始顺序排好
out: list[str] = []
pos = 0
while True:
w, h = next(sizes), next(sizes) # x 方向、y 方向瓷砖数
if w == 0 and h == 0: # "0 0" 表示输入结束
break
# 连续取 h*w 个瓷砖字符，再按每行 w 个切成网格
grid = [''.join(tiles[pos + r * w:pos + (r + 1) * w]) for r in range(h)]
pos += h * w
# 起点字符 '@' 在每个数据集合中唯一出现一次
start = next((r, c) for r in range(h) for c in range(w) if grid[r][c] == START)
out.append(str(count_reachable(grid, h, w, start)))
print('\n'.join(out))
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-05 05:42
* update_at: 2026-10-05 05:42
*/
// 红与黑：从 @ 出发做一次洪水填充，统计起点所在连通分量的黑砖数（含起点）。
#include <cstdio>
typedef long long ll;
const int MAXN = 25;
const int DIRS[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上、下、左、右四个相邻方向
char grid[MAXN][MAXN]; // 网格，已访问的黑砖就地染色成 '#'，不需要额外的 visited 数组
ll stack_r[MAXN * MAXN]; // 待展开格子的行坐标
ll stack_c[MAXN * MAXN]; // 待展开格子的列坐标
// 从 (sr, sc) 出发洪水填充，返回能到达的黑砖数（包含起点）
ll flood_fill(ll h, ll w, ll sr, ll sc) {
ll top = 0;
stack_r[top] = sr;
stack_c[top] = sc;
top++;
grid[sr][sc] = '#'; // 入栈即染色，保证同一个点不会被重复压栈
ll count = 0;
while (top > 0) {
top--;
ll r = stack_r[top];
ll c = stack_c[top];
count++; // 弹出即计数，每个可达黑砖恰好出栈一次
for (ll d = 0; d < 4; d++) {
ll nr = r + DIRS[d][0];
ll nc = c + DIRS[d][1];
if (nr < 0 || nr >= h || nc < 0 || nc >= w) continue; // 越界
if (grid[nr][nc] != '.') continue; // 不是可走的黑砖
grid[nr][nc] = '#';
stack_r[top] = nr;
stack_c[top] = nc;
top++;
}
}
return count;
}
int main() {
while (1) {
ll w, h;
scanf("%lld %lld", &w, &h);
if (w == 0 && h == 0) break; // 一行读入两个零表示输入结束
ll sr = -1, sc = -1; // 起点 @ 的坐标，每个数据集合中唯一出现一次
for (ll r = 0; r < h; r++) {
scanf("%s", grid[r]);
for (ll c = 0; c < w; c++) {
if (grid[r][c] == '@') {
sr = r;
sc = c;
}
}
}
printf("%lld\n", flood_fill(h, w, sr, sc));
}
return 0;
}