A25239. 编程实现：有一块矩形土地被划分成 n 行 m 列的网格，每个网格生长一种植物。如果相邻（上、下、左、右）网格生长的植物相同，那么这些网格的植物归为同一片植物林；如果一个网格与相邻网格生长的植物都不同，那么该网格的植物单独为一片植物林。例如：n = 3，m = 4；3 行 4 列的网格生长的植物如下：一共有 5 片植物林（已用不同颜色的线条圈出），如下图所示：给定 n 行 m 列的网格中生长的植物…
填空题
容易
知识点
题目描述
编程实现：
有一块矩形土地被划分成 n 行 m 列的网格，每个网格生长一种植物。如果相邻（上、下、左、右）网格生长的植物相同，那么这些网格的植物归为同一片植物林；如果一个网格与相邻网格生长的植物都不同，那么该网格的植物单独为一片植物林。
例如：n = 3，m = 4；3 行 4 列的网格生长的植物如下：
一共有 5 片植物林（已用不同颜色的线条圈出），如下图所示：
给定 n 行 m 列的网格中生长的植物，请找出一共有多少片植物林。
输入描述：
第一行输入两个整数 n、m（1≤n、m≤100），表示这块矩形土地被划分成的网格行数和列数，整数之间以一个空格隔开；
接下来输入 n 行，每行 m 个整数（1≤整数≤10000），表示每个网格的植物，不同的整数表示不同的植物，相同的整数表示相同的植物，整数之间以一个空格隔开。
输出描述：
输出一个整数，表示这块矩形土地一共有多少片植物林。
样例输入：
3 4
1 2 2 1
1 1 2 1
3 3 3 2样例输出：
5参考答案
from collections import deque
n, m = map(int, input（ ）.split（ ）)
grid = [list(map(int, input（ ）.split（ ）)) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
count = 0
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
for i in range(n):
for j in range(m):
if not visited[i][j]:
count += 1
queue = deque([(i, j)])
visited[i][j] = True
plant = grid[i][j]
while queue:
x, y = queue.popleft（ ）
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and grid[nx][ny] == plant:
visited[nx][ny] = True
queue.append((nx, ny))
print(count)答案解析
BFS 遍历网格，对每个未访问点启动搜索，标记连通区域。
相邻且植物相同的点属于同一连通块。
连通块数量即为答案。
上一题
下一题