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

610 阅读 0 评论 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分

1 人评分

本文分类：题解列表
浏览次数：610 次浏览
发布日期：2022-04-08 20:01:42
本文链接：https://blog.dotcpp.com/a/86505

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

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

评论列表共有 0 条评论

发表评论取消回复

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

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复