bfs 遍历每个岛屿

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1010;

typedef pair<int,int> pii;

char g[N][N];//地图
int sum, n;//岛屿数量 和 地图边界
bool st[N][N];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int res;//不会被淹没的岛屿数量

queue<pii> q;

int count()
{
     int cnt = 0;//一共的岛屿数量
     for (int i = 1; i < n; i ++ )
        for (int j = 1; j < n; j ++ )
        {
            if(!st[i][j] && g[i][j] == '#')//遇到陆地并且之前没有被遍历过
            {
                bool judge = false;//判断是否会被淹没
                cnt ++;//岛屿数量加一 并且遍历整个岛屿
                q.push({i, j});

                while(q.size())
                {
                    auto t = q.front();
                    q.pop();

                    for (int k = 0; k < 4; k ++ )
                    {
                        int a = t.first + dx[k], b = t.second + dy[k];
                        if(!st[a][b] && a >= 0 && b >= 0 && a < n && b < n && g[a][b] == '#')
                        {
                            q.push({a, b});
                            st[a][b] = true;

                            bool flag = false;//判断四个方向是否有海水
                            for(int w = 0; w < 4; w ++ )
                            {
                                int c = a + dx[w], d = b + dy[w];
                                if(g[c][d] == '.') {flag = true;break;}
                            }
                            if(!flag && !judge) res ++,judge = true;//如果四个方向都是陆地 这个岛屿不会被淹没
                        }
                    }
                }

            }
        }

        return cnt;
}

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

    cout << count() - res << endl;//总岛屿个数 减去 不会被淹没的个数

    return 0;
}