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

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

蓝桥杯 全球变暖【第九届】【省赛】【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;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/562803.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表(0条)

保存