本题是经典的网格连通块计数,考查 DFS / BFS 与 8 连通。
海拔严格大于洪水高度 X 的格子视为高地;高地之间若在水平、垂直或斜向相邻(八个方向),则属于同一救援区域。目标是统计这样的区域个数。
在 count_undisasterd_areas 中:
某地区发生特大洪水,水位高达 X,该地区被划分成了 m×n 个区块,各区块海拔高度不同。
被洪水淹没区域的群众已经自发转移到附近的高地,消防官兵需要快速获取未被淹没的高地数量,并派出救援队将群众转移。请你快速帮助消防官兵统计出未被淹没的高地数量,方便消防官兵组织救援。
未淹没的连续区块被识别为同一区域,连续方式包含水平、垂直、斜线方向(8 连通)。
参数 1:整数 X,表示洪水高度(0≤X≤10)。
参数 2:整数 m,表示区块的行数(3≤m,n≤100)。
参数 3:整数 n,表示区块的列数(3≤m,n≤100)。
参数 4:二维数组(m×n),表示每个区块的海拔高度。
一个整数,表示未被淹没的高地区域数量。
输入
5,3,3,[[0,0,0],[0,9,0],[0,0,0]]
输出
1
说明
只有一个区块高度(9),大于洪水高度(5),因此返回 1!
输入
3,5,5,[[2,2,2,2,2],[2,9,9,9,2],[2,9,9,9,2],[2,9,9,9,2],[2,2,2,2,2]]
输出
1
说明
如下矩阵,只有一个中间连续区块高度(9)大于洪水高度 5,因此返回 1。
22222
29992
29992
29992
22222
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册