网站做seo第一步,企业网站源码简约,注册会计师报名,沈阳软件定制开发✍个人博客#xff1a;https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 #x1f4da;专栏地址#xff1a;蓝桥杯题解集合 #x1f4dd;原题地址#xff1a;全球变暖 #x1f4e3;专栏定位#xff1a;为想参加蓝桥杯的小伙伴整理常考算法题解#xff0c;祝大家… ✍个人博客https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 专栏地址蓝桥杯题解集合 原题地址全球变暖 专栏定位为想参加蓝桥杯的小伙伴整理常考算法题解祝大家都能取得理想成绩 ❤️如果有收获的话欢迎点赞收藏您的支持就是我创作的最大动力 问题描述 你有一张某海域 N×N 像素的照片”.”表示海洋、”#”表示陆地如下所示 .......
.##....
.##....
....##.
..####.
...###.
.......其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿例如上图就有 2 座岛屿。 由于全球变暖导致了海面上升科学家预测未来几十年岛屿边缘一个像素的范围会被海水淹没。 具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)它就会被淹没。 例如上图中的海域未来会变成如下样子 .......
.......
.......
.......
....#..
.......
.......请你计算依照科学家的预测照片中有多少岛屿会被完全淹没。 输入格式 第一行包含一个整数 N。 以下 N 行 N 列包含一个由字符”#”和”.”构成的 N×N 字符矩阵代表一张海域照片”#”表示陆地”.”表示海洋。 照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。 输出格式 一个整数表示答案。 数据范围 1≤N≤1000 输入样例1 7
.......
.##....
.##....
....##.
..####.
...###.
.......输出样例1 1输入样例2 9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........输出样例2 1思路
这道题是一道经典的 bfs 问题我们可以通过计算每个岛屿的大陆边缘的像素数即靠海的像素和该岛屿大陆的总像素数然后判断两者是否相等如果相等则说明该岛屿的所有大陆像素都靠海即会被淹没。具体思路如下
遍历地图上的每个字符如果遇到了 # 则说明发现了岛屿进行 bfs 相关操作。本题用 bfs 来计算岛屿大陆边缘的像素数以及大陆总像素数只要发现一个像素的旁边出现了 . 则说明它靠海即是大陆边缘像素。判断上述两个像素数是否相等如果相等则答案数加一。
就拿题目的第一个样例举例其地图如下所示 通过观察可以发现上面存在两个岛屿我们用 bfs 来计算第一个岛屿即左上角那个岛屿可以发现大陆边缘像素数是等于大陆总像素数即都为 4故该岛屿未来会被淹没而第二个岛屿即右下角那个岛屿其大陆边缘像素数为 8而大陆总像素数为 9故大陆总像素数要大于边缘像素数该岛屿未来不会被淹没。如下图所示红色区域代表大陆边缘像素 因此该样例的答案为 1即只有 1 个岛屿未来会被淹没。
代码
#includebits/stdc.h
using namespace std;#define x first
#define y secondtypedef pairint, int PII;
const int N 10010;
char g[N][N];
bool st[N][N] { 0 };
int n;int dx[4] { -1,0,1,0 }, dy[4] { 0,1,0,-1 };
void bfs(int sx, int sy, int total, int bound)
{queuePII q;q.push({ sx,sy }); //初始化st[sx][sy] true;while (!q.empty()){auto t q.front();q.pop();total; //大陆总像素加1bool is_bound false;//判断上下左右是否可以前进for (int i 0; i 4; i){int x t.x dx[i], y t.y dy[i];//坐标不能越界if (x 0 || x n || y 0 || y n) continue;//已经走过的地方不能再走if (st[x][y]) continue;//如果是海洋则之前的那块像素坐标即(t.x,t.y)是大陆if (g[x][y] .){is_bound true;continue;}q.push({ x,y });st[x][y] true;}if (is_bound) bound; //大陆边缘像素加1}
}int main()
{cin n;for (int i 0; i n; i) scanf(%s, g[i]);//计算会被淹没的岛屿数int cnt 0;for (int i 0; i n; i){for (int j 0; j n; j){//只有没被访问过的像素以及该坐标为大陆才算作新岛屿if (!st[i][j] g[i][j] #){int total 0, bound 0;bfs(i, j, total, bound);//大陆总像素数等于大陆边缘像素数if (total bound)cnt;}}}cout cnt endl;return 0;
}
