算法分析

连通块问题 dfs或者bfs搜

时间复杂度 O(n2)

自己写的 dfs
感觉很巧妙 哈哈

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N][N];
int vis[N][N];
int n;
int ans;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool flag = false;
void dfs(int x, int y) {
    int cnt = 0;
    vis[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nowx = x + dx[i];
        int nowy = y + dy[i];
        if (nowx < 0 || nowx >= n || nowy < 0 || nowy >= n) {
            cnt++;
            continue;
        }
        if (a[nowx][nowy] == '#') 
            cnt++;
        if(a[nowx][nowy]=='#'&&!vis[nowx][nowy])
        dfs(nowx, nowy);

        if (cnt == 4) {
            flag = true;
        }
    }
    return;

}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == '#'&&!vis[i][j]) {
                dfs(i, j);
                if (flag == false) {
                    ans++;
                }
                flag = false;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

y总写的bfs

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 1010;

int n;
char g[N][N];
bool st[N][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 };
    st[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 (st[x][y])continue;
            if (g[x][y] == '.') {
                is_bound = true;
                continue;
            }
            q[++tt] = { x,y };
            st[x][y] = true;
        }
        if (is_bound)
            bound++;
    }

}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%s", g[i]);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!st[i][j] && g[i][j] == '#') {
                int total = 0, bound = 0;
                bfs(i, j, total, bound);
                if (total == bound)cnt++;
            }
        }
    }
    printf("%d\n", cnt);

    return 0;

}