【题解】全球变暖

题目链接：全球变暖

判断淹没

1. 题目要求最后输出剩多少岛屿未被淹没，只需要统计总共多少岛屿和被淹没多少岛屿，两者之差就是答案。
2. 如何统计岛屿总数和有多少岛屿被淹没？用 cnt 表示岛屿总数，用 ans 表示有多少岛屿 被淹没。遍历整个海域，每遇到新的岛屿就让 cnt 加 1 ，同时做 BFS 操作，标记该点所在岛屿的所有点，如果在标记的过程中发现有一点上下左右全部为陆地，说明该岛屿不会被完全淹没，让 ans 加 1 。

BFS C++ 615ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1e3 + 10;

int n;
string g[N];
bool st[N][N];
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};

bool bfs(int sx, int sy)
{
    queue<PII> q;
    q.push({sx, sy});
    st[sx][sy] = true;
    
    bool Flag = false;
    while (q.size())
    {
        int x = q.front().x, y = q.front().y;
        q.pop();
        
        bool flag = true;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= n || b >= n || a < 0 || b < 0 || g[a][b] == '.') 
            {
                flag = false;
                continue;
            }
            if (st[a][b]) continue;
            
            st[a][b] = true;
            q.push({a, b});
        }
        if (flag) Flag = true;
    }
    return Flag;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    int sum = 0, ans = 0;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
        {
            if (!st[i][j] && g[i][j] == '#')
            {
                sum ++ ;
                if (bfs(i, j)) ans ++ ;
            }
        }
    }
    
    cout << sum - ans << endl;
    return 0;
}