从每个未访问的草格开始四连通 BFS 并标记，统计连通草丛数量。
OJ: noi_openjudge
题目 ID: ch0108-17
难度:普及-
标签:图论搜索矩阵python
日期: 2026-07-30 23:01
题意
统计牧场中由公共边连通的 # 草格形成的草丛数量。
思路
扫描到未访问的 # 时，答案加一并从它出发做四方向 BFS，把同一连通块改为 .。之后再次扫描到的草格一定属于新草丛。
代码
cpp
#include <cstdio>
int n,m;
char grass[200][200];
int cnt=0;
int fx[4][2] = { 0,-1, -1,0, 1,0, 0,1 };
void init(){
scanf("%d%d",&n,&m);
int i,j;
for (i=1;i<=n;i++){
scanf("%s",grass[i]+1);
}
}
int main(){
init();
int i,j,k;
for (i=1;i<=n;i++){
for (j=1;j<=m;j++){
if( grass[i][j] == '#'){
cnt++;
for (k=0;k<=3;k++){
grass[ i+ fx[k][0] ][j + fx[k][1] ] = '.';
}
}
}
}
printf("%d\n",cnt);
return 0;
}复杂度
总结
Python代码
python
from collections import deque
row_count, column_count = map(int, input().split())
field = [list(input().strip()) for _ in range(row_count)]
clump_count = 0
for row in range(row_count):
for column in range(column_count):
if field[row][column] != "#":
continue
clump_count += 1
field[row][column] = "."
queue = deque([(row, column)])
while queue:
current_row, current_column = queue.popleft()
for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
next_row, next_column = current_row + dx, current_column + dy
if 0 <= next_row < row_count and 0 <= next_column < column_count and field[next_row][next_column] == "#":
field[next_row][next_column] = "."
queue.append((next_row, next_column))
print(clump_count)C++代码
cpp
#include <cstdio>
int n,m;
char grass[200][200];
int cnt=0;
int fx[4][2] = { 0,-1, -1,0, 1,0, 0,1 };
void init(){
scanf("%d%d",&n,&m);
int i,j;
for (i=1;i<=n;i++){
scanf("%s",grass[i]+1);
}
}
int main(){
init();
int i,j,k;
for (i=1;i<=n;i++){
for (j=1;j<=m;j++){
if( grass[i][j] == '#'){
cnt++;
for (k=0;k<=3;k++){
grass[ i+ fx[k][0] ][j + fx[k][1] ] = '.';
}
}
}
}
printf("%d\n",cnt);
return 0;
}复杂度
每格至多入队一次，时间复杂度为
总结
连通块计数的标准模式是“发现未访问点，搜索并标记整块”。