首页 > 试题广场 >

挡住洪水

[编程题]挡住洪水

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

$\hspace{15pt}$ 吴铭市近日洪水肆虐，洪水从地图外部渗入。市政部门在若干方格上砌起围墙，用 `*` 表示。若某片空地区域不与地图边界四联通（上下左右方向），则不会被洪水淹没，视为安全空地。

$\hspace{15pt}$ 地图用大小为 $x \times y$ 的字符矩阵描述：`'*'` 表示围墙，`'0'` 表示空地。所有相互四联通的 `'0'` 构成一个区域。请统计所有安全空地格子的数量之和（即所有不与边界四联通的 `'0'` 的总数）。

输入描述:

第一行输入两个整数 。
接下来  行，每行  个字符，组成围墙建设图，仅含 `'*'` 与 `'0'`。

输出描述:

输出一个整数，表示所有安全空地格子的总数。

示例1

输入

2 2
**
**

输出

算法知识视频讲解

Python3

xjh_ustc

from collections import deque
n,m = map(int,input().split())
grid = []
for i in range(n):
    grid.append(input().strip())
visited = [[False]*m for _ in range(n)]
dire = [(-1,0),(1,0),(0,-1),(0,1)]
cnt = 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == '0' and not visited[i][j]:
            dq = deque([(i,j)])
            visited[i][j] = True
            is_safe = True
            size = 1
            while dq:
                x,y = dq.popleft()
                if x==0 or x==n-1 or y==0 or y==m-1:
                    is_safe = False
                for dx,dy in dire:
                    nx,ny=x+dx,y+dy
                    if 0<=nx<n and 0<=ny<m:
                        if not visited[nx][ny] and grid[nx][ny]=='0':
                            visited[nx][ny]=True
                            dq.append((nx,ny))
                            size += 1
            if is_safe:
                cnt +=size
print(cnt)

发表于 2025-09-04 19:26:34 回复(0)

Python3

tjss666一号

这个题确实有歧义，这个地方统计的是安全区域中的0的个数

n,m = map(int, input().split())
if 1 <= n < 3&nbs***bsp;1 <= m < 3:
    print(0)
    quit()
s,dirs,sum1 = [],[(1,0),(0,1),(-1,0),(0,-1)],0
for i in range(n):
    s.append(list(input().replace('*','X')))      
def dfs(i,j):
    stack = [(i,j)]
    an = True
    shu = 1
    while stack:
        nx,ny = stack.pop()
        for dx,dy in dirs:
            x = nx+dx
            y = ny+dy
            if s[x][y] == '0':
                if x == 0&nbs***bsp;x == n-1&nbs***bsp;y == 0&nbs***bsp;y == m-1:
                    s[x][y] = 'X'
                    an = False
                elif 0 < x < n-1 and 0 < y < m-1:
                    s[x][y] = 'X'
                    shu += 1
                    stack.append((x,y))
    if an:
        return shu
    else:
        return 0
for i in range(n):
    for j in range(m):
        if s[i][j] == '0' and 0 < i < n-1 and 0 < j < m-1:
            s[i][j] = 'X'
            sum1 += dfs(i,j)
print(sum1)

首先n和m随便一个小于3都绝对不行，因为这个题的在边界上所有的0都会导致区域无效，因为只需要解决一次案例所以我用的quit直接退出，如果数据组数很多就不要这样做。然后就是经典的列表、dirs方向和和sum1。为了在过程中输出矩阵内容更直观，我把*换成了X，这样所有的元素都会很齐整。然后就是绝对dfs加栈遍历，对每一个dfs(i,j)记为一个区域，所以开头就写出an和shu，之后不用管s[x][y]为X的情况，因为对题目没有如何影响，你可以想一想，假如有一个区域含0，他不是安全区域的可能只有有边界0的情况，不然就一定是安全的，所以判断边界，如果不是边界就计数并append方便循环，最后return 0 或者 shu也是经典方法了，这样方便sun1累加。注意最后一定要是0而且不是边界的时候才dfs，这是寻找安全区域的基本条件，并且就是因为提前找到了一个0，dfs中shu必须从1开始

发表于 2025-08-17 11:35:57 回复(0)

提交观点

问题信息

广度优先搜索(BFS)

难度：

3条回答 14收藏 541浏览

挡住洪水

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题