AcWing 1233. 全球变暖
原题链接
简单
作者:
冉俊泽
,
2021-02-12 18:13:12
,
所有人可见
,
阅读 261
#include<iostream>
#include<cstdio>
#include<string>
#define x first
#define y second
using namespace std;
typedef pair<int, int>PII;
const int N = 1010;
char str[N][N];
bool vis[N][N];
int n;
PII q[N * N];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
void bfs(int sx, int sy, int &total, int &bound)
{
int hh = 0, tt = 0;
q[0] = {sx, sy};
vis[sx][sy] = true;
while(hh <= tt)
{
PII t = q[hh++];
total++;
bool 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(vis[x][y]) continue;//访问过
if(str[x][y] == '.')
{
is_bound = true;
continue;
}
q[++tt] = {x, y};
vis[x][y] = true;
}
if(is_bound) bound++;
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%s", str[i]);
int cnt = 0;//表示消失的岛屿个数
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(!vis[i][j] && str[i][j] == '#')
{
int total = 0, bound = 0; //记录,岛屿的#个数和#是边界的个数
bfs(i, j, total, bound);
//如果total==bound那么该岛屿将会消失
if(total == bound) cnt++;
}
}
}
printf("%d\n", cnt);
return 0;
}