网格连通块计数入门题：按行扫描遇到未抹掉的非 0 数字就数一个新细胞，BFS 把整个四连通块原地抹成 0 当访问标记，每格至多入队一次。
OJ: roj
题目 ID: 1329
难度:入门
标签:搜索BFS连通块
创建: 2026-09-30 05:33
更新: 2026-10-05 10:01
后置题目
roj 3080武士风度的牛B 的网格 BFS 直接沿用 A 教的「入队即标记、标记兼作访问、每格至多入队一次」这一状态设计（main.py 里先写 dist[nxt] = dist[pos] + 1 再 append），只是把标记从原地抹 '0' 换成 dist 初值 -1，并叠加马的 8 种跳跃位移与首次够到 H 即最短距离这一判定。roj 3081乳草的入侵B 的八连通 BFS 直接复用 A 教的「入队即标记、每格至多入队一次」这一 BFS 不变式来替代逐周全图重扫，只在其上叠加八方向扩散与取最大层数作为答案，属同为 BFS 模板但强度提升一级的台阶关系。roj 1359围成面积B 的多源洪水填充直接复用 A 教的那一步——四连通网格 flood fill「入队即标记、每格至多入队一次」的状态设计（B 的代码同样是 outside 置真后才 append），只是把种子从单个细胞格换成网格最外圈的全部 0 格，并把染色对象由细胞翻转为外部格后再数剩余 0。roj 1250The CastleB 直接复制 A 教的「扫描种子格 + 洪水填充整块并计数」骨架，只把连通条件换成墙位判定、再额外统计分量大小求最大值roj 1248Dungeon MasterB 的三维六方向 BFS 直接沿用 A 明确点名为「可迁移实现习惯」的入队即标记状态设计（B 代码在 push 前写 seen=true），保证每格只展开一次，只在其上叠加层号当最短分钟数、多组数据解析与三维坐标偏移扩展。roj 1191流感传染B 的多源 BFS 扩散直接沿用 A 教的入队即标记（每格至多入队一次，原地改格子当访问标记），只是在其上叠加按天分层同步这一额外流程shumeng CSP201409D最优配餐B 的多源 BFS 直接复用 A 教的网格 BFS「入队即标记、每格至多入队一次」这一状态设计（B 代码同样在入队时写 dist 并靠 dist!=INF 阻止重复入队），据此保证每个格点只被首次到达一次，从而把首次到达的层数当作到最近分店的最短距离，只在其上叠加多源起点与按需求量计费。shumeng CSP201512C画图B 的填充操作直接复用 A 教的四连通 flood fill 从种子格扩散并维护访问标记这一步，main.cpp 的 flood_fill 同样是 dx/dy 四方向入队，只是把可扩散条件从「不是 '0'」换成「不是线段 - | +」，并叠加画线模拟与坐标倒序输出这些新流程，难度仅升一级（入门→普及-）。luogu P1162填涂颜色A 教的『邻居在界内且不是 0 就改值并入队』的入队即标记 flood fill，被 B 解法二的 BFS2 原样用来把整片内部 0 区域改写成 2，B 只在此基础上叠加补边框/正难则反判内外。
题目描述
给定一个 0 到 9。非 0 的数字代表细胞；上下左右相邻（四连通，不含对角线）的细胞数字属于同一细胞，求矩阵中细胞的个数。
输入：第一行为行数 4）：
text
4 10
0234500067
1034560500
2045600671
0000000089思路
按行扫描矩阵，遇到还没抹掉的非 0 格子，说明它所属的细胞尚未统计，计数加一，并从它出发做 BFS：把整个四连通块原地抹成 0 当访问标记（入队即抹掉，保证每格至多入队一次），避免重复计数。总时间复杂度
参考代码
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-02-14 10:30
# update_at: 2026-10-04 15:03
import sys
from collections import deque
def flood_fill(grid: list[list[str]], sr: int, sc: int) -> None:
"""从 (sr, sc) 出发把整个四连通细胞抹成 '0'（原地标记，避免 visited 数组）。"""
grid[sr][sc] = '0'
queue = deque([(sr, sc)])
while queue:
r, c = queue.popleft()
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
inside = 0 <= nr < len(grid) and 0 <= nc < len(grid[0])
if inside and grid[nr][nc] != '0':
grid[nr][nc] = '0' # 入队即标记，保证每格至多入队一次
queue.append((nr, nc))
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
n, m = int(next(data)), int(next(data)) # 两个位置量先命名
grid = [list(next(data).decode()) for _ in range(n)] # 每行是完整 token，行内无空格
cells = 0
for r in range(n):
for c in range(m):
is_cell = grid[r][c] != '0' # 尚未抹掉的细胞数字 = 一个新细胞的种子
if is_cell:
cells += 1
flood_fill(grid, r, c)
print(cells)
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 10:02
* update_at: 2026-10-05 10:02
*/
#include <cstdio>
typedef long long ll;
const int MAXN = 105; // 行数上限
const int MAXM = 105; // 列数上限
int n, m;
char a[MAXN][MAXM]; // a[r][c]：第 r 行第 c 列的字符，'0' 表示背景，'1'~'9' 是细胞数字
int q[MAXN * MAXM][2]; // BFS 队列，q[i][0]=行，q[i][1]=列；每格至多入队一次
int dr[4] = {-1, 1, 0, 0}; // 四个方向的行偏移
int dc[4] = {0, 0, -1, 1}; // 四个方向的列偏移
// 从 (sr, sc) 出发，把这个四连通细胞全部原地抹成 '0'（省掉 visited 数组）
void flood_fill(int sr, int sc) {
int head = 0, tail = 0;
a[sr][sc] = '0';
q[tail][0] = sr;
q[tail][1] = sc;
tail++;
while (head < tail) {
int r = q[head][0];
int c = q[head][1];
head++;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m)
continue;
if (a[nr][nc] == '0')
continue;
a[nr][nc] = '0'; // 入队即标记，保证每格至多入队一次
q[tail][0] = nr;
q[tail][1] = nc;
tail++;
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int r = 0; r < n; r++)
scanf("%s", a[r]);
int cells = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
if (a[r][c] != '0') { // 还没抹掉的细胞数字 = 一个新细胞的种子
cells++;
flood_fill(r, c);
}
}
}
printf("%d\n", cells);
return 0;
}