蓝桥杯 全球变暖【第九届】【省赛】【B组】

蓝桥杯 全球变暖【第九届】【省赛】【B组】

• 题意
• 解题思路
• 代码

题目地址1
题目地址2
宽度优先搜索bfs查找连通块的简单应用

题意

你有一张N * N的照片，.代表海洋，#代表陆地，其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿，与海洋相邻的陆地会被淹没，求照片中有多少岛屿会被完全淹没。

解题思路

由题意可知，一块陆地只要和上下左右有海洋就会被淹没，所以只要一个岛屿中有一块陆地被上下左右四个陆地包围，这个岛屿就不会完全淹没
而求一个岛屿即为在图中查询连通块
所以题目的要求就会转化为两个问题
①在图中有多少多个连通块
②哪些连通块中存在一个位置四边相邻的都是#.
所以我们只需要遍历一遍图，用数组d[x][y]存当前位置是否遍历过，查询到#，用 bfs 查询连通块，d[x][y] = 1标记该位置被遍历，用res = 1表示该连通块有被#包围的#。

注：
auto

代码

#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define ll long long
typedef pair<int, int> PII;

const int N = 1e3 + 10;

int n;
//存图
char g[N][N];
//四个方向
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
//查询是否遍历过
int d[N][N];
//该岛屿中是否有被陆地包围的陆地
int res = 0;

//用 bfs 查询连通块（ dfs 也可以）
int bfs(int x, int y)
{
	//标记该位置被遍历
    d[x][y] = 1;
    res = 0;
    queue<PII> q;
    q.push({ x,y });
    while (q.size()) {
    	//C++11的语法
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int a = t.first + dx[i], b = t.second + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < n && g[a][b] == '#' && d[a][b] == -1) {
                q.push({ a,b });
                //该位置被并入当前连通块
                d[a][b] = 1;
                //如果有一块陆地上下左右都为陆地 res=1
                if (g[a - 1][b] == '#' && g[a][b - 1] == '#' && g[a + 1][b] == '#' && g[a][b + 1] == '#') {
                    res = 1;
                    //cout << a << ' ' << b << endl;
                }
            }
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }
    int ans = 0;
    memset(d, -1, sizeof(d));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
        //如果该位置是陆地并且没有被遍历过
            if (g[i][j] == '#' && d[i][j] == -1) {
            	//返回值是res，res为0说明该岛屿没有被陆地包围的陆地
                if (bfs(i, j) == 0)ans++;
            }
        }
    }
    cout << ans << endl;
	return 0;
}