zqm

用户名：uq_71512143721

访问量：1517

签　名：

等　　级
排　　名	5018
经　　验	1605
参赛次数	0
文章发表	8
年　　龄	0
在职情况	学生
学　　校	克莱登大学
专　　业	计算机哲学

　　自我简介：

TA的其他文章

兰顿蚂蚁【Python解法】【清晰简洁】【20+行】
浏览：480

【2018 蓝桥杯】全球变暖【BFS】【Python解法】
浏览：474

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

【2018 蓝桥杯】全球变暖【BFS】【Python解法】

　　作者: zqm　　　　发表时间：2022-04-08 20:01:42 浏览：474　|　评论：0　

原题链接：蓝桥杯2018年第九届真题-全球变暖

思路很清晰。

1. 遍历图中所有的点，遇到 “#”， 代表是岛屿的区块。
2. 用 bfs 向外扩展岛屿，遇到海就停住。 （使用一个 vis 记录遍历过的点）
3. 在遍历一个岛屿的过程中，同时记录不会被淹没区块的数量：实现一个 flood 函数判断区块的上下左右是否是海洋。
4. bfs 返回剩余区块的数量。 返回若为零代表完全被淹没。

几个注意的点：
1. 题目问的是被完全淹没的点的数量。我看成了剩余的岛屿的数量，结果因为给的样例两种情况都是一就弄错了。
2. 注意需要单独判断一下起始点是否会被淹没来决定区块数量的初始化值。（也可以不标记在后续的点中被搜索到。）

```python
import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
sea = [list(input().strip()) for _ in range(n)]

direct = [(0, 1), (1, 0), (-1, 0), (0, -1)]
vis = [[False]*n for _ in range(n)]

def check(x, y):
    if (x<0 or y<0 or x>=n or y>=n): return False
    if (vis[x][y]): return False
    if (sea[x][y]=="."): return False
    return True
def flood(x, y):
    for dx, dy in direct:
        nx, ny = x + dx, y + dy
        if (nx<0 or ny<0 or nx>=n or ny>=n): continue
        if(sea[nx][ny]=="."): return True
    return False
def bfs(x ,y):
    q = deque()
    q.append((x, y))
    blocks = 0 if flood(x, y) else 1
    while q:
        tx, ty = q.popleft()
        for dx, dy in direct:
            nx, ny = tx + dx, ty + dy
            if(check(nx, ny)):
                vis[nx][ny] = True
                q.append((nx, ny))
                if(not flood(nx, ny)): blocks+=1
    return blocks
res = 0
for x in range(n):
    for y in range(n):
        if(sea[x][y]=="#" and not vis[x][y]):
            vis[x][y] = True
            rest = bfs(x, y)
            if(rest==0): res+=1
print(res)
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zqm

TA的其他文章

你可能喜欢

字符逆序（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

母牛的故事（C语言代码）

点我有惊喜！你懂得！

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

【2018 蓝桥杯】全球变暖【BFS】【Python解法】

评论区

精彩推荐

C语言训练-排序问题<1> （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

1005答案错误为什么

C语言程序设计教程（第三版）课后习题7.2 （C++代码）

简单的a+b （C语言代码）

C语言训练-求素数问题（C语言代码）

zqm

TA的其他文章

你可能喜欢

字符逆序 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C++代码）

母牛的故事 （C语言代码）

点我有惊喜！你懂得！

字符串输入输出函数 （C++代码）（都当成字符串吧hhhhhhhh）

【2018 蓝桥杯】全球变暖【BFS】【Python解法】

评论区

精彩推荐

C语言训练-排序问题<1> （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

1005答案错误为什么

C语言程序设计教程（第三版）课后习题7.2 （C++代码）

简单的a+b （C语言代码）

C语言训练-求素数问题 （C语言代码）

字符逆序（C语言代码）

母牛的故事（C语言代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

　　评论区

C语言训练-计算1~N之间所有奇数之和（C语言代码）

C语言训练-求素数问题（C语言代码）