全球变暖 BFS
全球变暖
问题描述
给定一张 N×N 像素的海域照片，其中：
.表示海洋#表示陆地
岛屿定义为上下左右四个方向上连通的陆地组成的区域。全球变暖导致岛屿边缘（即与海洋相邻的陆地）会被淹没。要求计算有多少岛屿会被完全淹没。
输入格式
- 第一行：整数 N (1 ≤ N ≤ 1000)
- 接下来 N 行：每行 N 个字符，表示海域照片
输出格式
- 一个整数，表示会被完全淹没的岛屿数量
示例
输入：
7 ....... .##.... .##.... ....... .##... ####... .###... .......输出：
1运行限制
- 最大运行时间：1s
- 最大运行内存：256M
解题思路
1️⃣ 遍历整个地图
2️⃣ 遇到一个没访问过的 #
👉 用 BFS / DFS 找出这一整座岛
3️⃣ 在搜索这座岛时：
1.统计总格子数 total
2.统计“挨着海水的格子数” flood
4️⃣ 搜完一整座岛后判断：
如果 total == flood
👉 说明所有点都在边缘
👉 这座岛会被完全淹没 ✅
5️⃣ 统计这样的岛数量
#include<bits/stdc++.h>usingnamespacestd;intn;vector<string>g;vector<vector<bool>>vis;intdx[4]={1,-1,0,0};intdy[4]={0,0,1,-1};voidbfs(intsx,intsy,int&total,int&flood){queue<pair<int,int>>q;q.push({sx,sy});vis[sx][sy]=true;while(!q.empty()){auto[x,y]=q.front();q.pop();total++;boolisFlood=false;for(intd=0;d<4;d++){intnx=x+dx[d];intny=y+dy[d];if(nx<0||nx>=n||ny<0||ny>=n)continue;if(g[nx][ny]=='.'){isFlood=true;}if(g[nx][ny]=='#'&&!vis[nx][ny]){vis[nx][ny]=true;q.push({nx,ny});}}if(isFlood)flood++;}}intmain(){cin>>n;g.resize(n);for(inti=0;i<n;i++){cin>>g[i];}vis.assign(n,vector<bool>(n,false));intans=0;for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(g[i][j]=='#'&&!vis[i][j]){inttotal=0,flood=0;bfs(i,j,total,flood);if(total==flood){ans++;}}}}cout<<ans<<endl;return0;}