蓝桥杯B组C++省赛 全球变暖【bfs】

题目描述:

你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:

.......
.##....
.##....
....##.
..####.
...###.
.......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。  

由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。  

例如上图中的海域未来会变成如下样子:

.......
.......
.......
.......
....#..
.......
.......

请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。  

【输入格式】

第一行包含一个整数N。  (1 <= N <= 1000)  
以下N行N列代表一张海域照片。  

照片保证第1行、第1列、第N行、第N列的像素都是海洋。

思路:此题采用bfs算法,找到每个岛屿的最大连通块,看是否四周都有陆地,有的话就不会被淹没,而被标记过得点就不用再以它为起点寻找连通块了。

代码如下:

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 1010;                         /定义像素规模
char mp[N][N];                               /记录像素内容
int vis[N][N];                                   /标记数组,标记是否访问过该点
int flag;                                          /如果四周全为陆地就设为1
int d[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };   /四个方向
void bfs(int x, int y)
{

    queue<pair<int, int>>q;           /用stl的队列创建存储点(x,y)
    q.push({ x,y });                           /把坐标推进队列
    vis[x][y] = 1;                               /访问过,设为1
    while (q.size()) {
        pair<int, int> t = q.front();            /取出第一个
        q.pop();                                         /把取出的从队列中弹出来
        int tx = t.first, ty = t.second;
        if (mp[tx][ty + 1] == '#'&&mp[tx][ty - 1] == '#'&&            /判断四周是否全为陆地
            mp[tx + 1][ty] == '#'&&mp[tx - 1][ty] == '#')
            flag = 1;
        for (int i = 0; i < 4; i++) {                          /向四周延伸连续块
            int nx = tx + d[i][0], ny = ty + d[i][1];
            if (vis[nx][ny] == 0 && mp[nx][ny] == '#')
            {
                vis[nx][ny] = 1;
                q.push({ nx,ny });
            }
        }

    }
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> mp[i];                     /坐标点输入
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (mp[i][j] == '#'&&vis[i][j] == 0) {
                flag = 0;                                      /用bfs函数找出连接块
                bfs(i, j);
                if (flag == 0)                             /flag为1代表全为陆地不会被湮没,为0就代表会被淹没,并计数
                    ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

上一篇:G - Find a way


下一篇:期货开户市场保持非理性状态