首页 > 试题广场 >

没挡住洪水

[编程题]没挡住洪水
  • 热度指数：4063 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}吴铭市近日洪水肆虐，然而市政部门紧急在若干方格上砌起围墙是豆腐渣工程，被洪水中的强腐蚀性物质一氧化二氢分解了，只剩下了用 `#` 表示的空地。

\hspace{15pt}地图用大小为 N \times N 的字符矩阵描述：`'.'` 表示已经被洪水淹没的区域，`'#'` 表示空地。四联通的 `'#'` 组成一个区域。

\hspace{15pt}聪明睿智的吴铭市防洪抗灾紧急委员会官员在全市防洪抗灾紧急会议上指出，在接下来的一天中，洪水仍将上涨，所有与已经被洪水淹没的区域相邻（上下左右方向）的空地格子都会被淹没。请计算在此次上涨后，吴铭市中将有多少个区域被完全淹没。

输入描述:
\hspace{15pt}第一行输入整数 N\left(1\leqq N\leqq 1000\right)。
\hspace{15pt}随后 N 行，每行 N 个字符构成吴铭市的地图，只含 `'.'` 与 `'#'`。已知边界四条边全部为已经被洪水淹没的区域。


输出描述:
\hspace{15pt}输出一个整数，表示一天后会完全消失的空地区域数量。
示例1

输入

1
.

输出

0
算法知识视频讲解
添加回答
Python3
余姚a头像 余姚a

#用例只通过五组, 期望有大佬指出问题所在
from collections import deque

N = int(input())
wumap = [list(input().strip()) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
q = deque()
# 多源
for i in range(N):
    for j in range(N):
        if wumap[i][j] == ".":
            q.append((i, j))

dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q:
    r, c = q.popleft()
    for x, y in dir:
        rx, cy = r + x, c + y
        if 0 <= rx < N and 0 <= cy < N and not visited[rx][cy] and wumap[rx][cy] == "#":
            visited[rx][cy] = True
            q.append((rx, cy))
# 被淹没的区域
def dfs(i, j):
    visited[i][j] = False
    for x, y in dir:
        rx, cy = i + x, j + y
        if 0 <= rx < N and 0 <= cy < N and visited[rx][cy] and wumap[rx][cy] == "#":
            dfs(rx, cy)

step = 0
for i in range(N):
    for j in range(N):
        if wumap[i][j] == "#" and visited[i][j]:
            step += 1
            dfs(i, j)

print(step)


发表于 2026-04-25 22:05:53 回复(0)
提交观点

问题信息

广度优先搜索(BFS)
难度：
1条回答 781浏览

热门推荐

相关试题

没挡住洪水

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号