解题思路
给定一个仅包含 0/1 的矩阵,0 表示平原,1 表示山地。矩阵外全部视为平原(0)。
“盆地”就是被山地在上下左右方向完全包围的平原区域,即这一片 0 的连通块不能与矩阵边界上的平原相连。要求输出所有盆地的平原格子数量之和。
典型做法是 Flood Fill(BFS/DFS 连通块搜索):
- 把矩阵中与“外部平原”连通的所有 0 标记掉。
P4477.第1题-计算盆地面积
题目内容
给定一个表示地图的矩阵,其中0表示平原,1表示山地。盆地的定义为被山地在水平和垂直方向完全包围的平原
1.要求计算盆地的面积,
2.矩阵范围之外均为平原
3.整个地图中可能包含多个盆地,
输入描述
第1行:M N
-
M是矩阵的宽,范围是[1,300]
-
N是矩阵的高,范围是[1,300]
第2到第N+1行:X1 X2...XM为矩阵的每行,每个元素的范围是[0,1]
输出描述
输出1个数字,表示盆地的面积
样例1
输入
7 7
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 1 1 0 1
1 0 1 0 1 0 1
1 0 1 1 1 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
输出
17
说明
第一行7 7:表示矩阵的宽和高分别为7和7
该矩阵描述的地图中,分别存在两个盆地,其中较小的盆地在较大盆地内部,总面积为17
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 1 1 0 1
1 0 1 0 1 0 1
1 0 1 1 1 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
样例2
输入
8 4
1 1 1 0 1 1 1 1
1 0 1 0 1 1 0 1
1 1 1 0 1 1 1 1
0 0 1 0 0 1 1 1
输出
2
说明
第一行8 4:表示矩阵的宽和高分别为8和4
该矩阵描述的地图中,分别存在两个盆地,其中较小的盆地在较大盆地内部,总面积为2
1 1 1 0 1 1 1 1
1 0 1 0 1 1 0 1
1 1 1 0 1 1 1 1
0 0 1 0 0 1 1 1
样例3
输入
8 4
0 0 1 0 1 0 0 0
0 0 1 0 0 1 0 0
1 1 1 0 0 1 1 1
0 0 0 0 0 0 0 0
输出
0
说明
第一行8 4:表示矩阵的宽和高分别为8和4
矩阵中没有构成闭环的盆地
样例4
输入
8 4
0 0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0
0 0 0 1 1 0 0 0
输出
4
说明
8 4:表示矩阵shape为8∗4