题目描述

blablabla

样例

blablabla

算法1

(BFS)

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1100;

bool st[N][N];
typedef pair<int,int> PII;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int ans = 0;
int n;

int main() {
    cin >> n;
    vector<string> g(n);
    for(auto &t:g) cin >> t;

    auto bfs = [&](int x, int y) -> void {
        st[x][y] = true;
        queue<PII> q;
        q.push({x,y});
        bool flag = false;
        while(q.size()) {
            auto t = q.front();
            q.pop();
            int a1 = t.first, b1 = t.second;
            if(g[a1][b1+1] == '#' && g[a1][b1-1] == '#' && g[a1-1][b1] == '#' && g[a1+1][b1] == '#') flag = true;

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

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

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla