题解 LGP8662 [蓝桥杯 2018 省 AB] 全球变暖

10
..........
.##.......
.###......
..##...##.
.###..###.
..#...###.
.###...#..
..#...###.
.......#..
..........

..........
..........
..#.......
..........
..#....#..
.......#..
..#.......
.......#..
..........
..........

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define elif else if

int n, s1 = 0, s2 = 0;//s1是开始时岛屿个数，s2是水面上涨后的
char c1[1005][1005], c2[1005][1005];//c1是开始时的形势，c2是水面上涨后的
int id[1005][1005] = {0};//id表示一个坐标本来属于哪个岛
//因为是否淹没某个坐标的判定需要原来的形势，所以水面上涨后需要另开一个数组
bool f[1005][1005] = {{false}};//记录到没到过某个坐标，初始都没到过
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};//四个方向，上下左右

//floodfill算法，走遍这个岛的每块陆地
//坐标：(x, y)，记录到c数组中（这样写其实是懒），这是第iid号岛（iid, island ID）
void srh(int x, int y, char c[1005][1005], int iid)
{
    f[x][y] = true;//标记到过了
    id[x][y] = iid;//标记是iid号岛
    for (int i = 0; i < 4; i++)
        if (1 <= x + dx[i] && x + dx[i] <= n && 
            1 <= y + dy[i] && y + dy[i] <= n && //如果没有越界
            c[x + dx[i]][y + dy[i]] == '#' && //并且还是陆地
            !f[x + dx[i]][y + dy[i]])//最后还没到过
            srh(x + dx[i], y + dy[i], c, iid);//那就搜过去
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> c1[i][j], c2[i][j] = c1[i][j];//复制一份
    //统计开始前有多少个岛
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)//枚举每个坐标
            if (c1[i][j] == '#' && !f[i][j])//如果是陆地并且没有统计到过
                srh(i, j, c1, ++s1);//统计一下
    //水面开始上涨了
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)//枚举每个坐标
            if (c1[i][j] == '#')//如果这一个地方是陆地，才继续
                for (int k = 0; k < 4; k++)//枚举上下左右
                    if (c1[i + dx[k]][j + dy[k]] == '.')//如果碰到了海
                    {
                        c2[i][j] = '.';//被淹没力
                        break;//再见
                    }
    //统计结束后还有多少个岛有残部
    map<int, int> mp;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (c2[i][j] == '#' && mp[id[i][j]] == 0)//发现一块残部并且之前没有发现其所属大岛的其他残部
                mp[id[i][j]] = 1;//标记这个岛有残部，注意是=1而不是++
    for (auto i : mp)//C++11及以上遍历STL容器的方法
        s2 += i.second;//统计有多少个岛有残部
    //最后，答案就是开始时的岛屿个数减去水面上涨后还剩的
    cout << s1 - s2 << endl;
    return 0;
}