首页 > 试题广场 >

数水坑

[编程题]数水坑

热度指数：1979 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

${\hspace{15pt}}$ 由于降雨，水在农夫约翰的田地里积聚成水坑。田地是一个 $N\times M$ 的矩形网格，每个格子要么是水 `W`，要么是干地 `.`。
${\hspace{15pt}}$ 若两个水格子在 八连通 （上下左右及四条对角线）意义下互达，则它们属于同一个水坑。
${\hspace{15pt}}$ 给出田地示意图，计算水坑数量。

输入描述:

第一行输入两个整数 。
接下来  行，每行  个字符组成的字符串，字符集为 `W` 与 `.`，中间无空格。

输出描述:

输出一行一个整数，即水坑的数量。

示例1

输入

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出

说明

共有三个水塘：一个在左上角，一个在左下角，还有一个沿着右侧。

算法知识视频讲解

Python3

丰川小祥有点乖

n, m = map(int, input().split(" ")) # 输入矩阵大小

map = [] # 定义地图

for _ in range(n): # 输入地图
    map.append(input().strip())

flag = [[False] * m for _ in range(n)] # 建立标记矩阵，等遇见一个水坑就打上一个标记
dirs = [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)] # 8个方向

num = 0 # 水坑数量

def dfs(x,y): # 每遇见一个水坑，就通过dfs把连通的所有水坑标记
    
    for dx, dy in dirs: # 循环尝试往8个方向移动
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < m and map[nx][ny] == "W" and not flag[nx][ny]: # 符合条件说明是水坑，打上标记
            flag[nx][ny] = True
            dfs(nx,ny)
    


for i in range(n): # 循环整个地图，遇见一个没打标记的水坑，就用dfs把所有水坑标记合成一个水塘，然后水塘数+1
    for j in range(m):
        if map[i][j] == "W" and not flag[i][j]:
            dfs(i,j)
            num += 1

print(num)

发表于 2025-10-13 18:54:36 回复(0)