大红~大紫~
查看原帖
大红~大紫~
794507
_VirtualPoint_楼主2023/7/28 14:27

![]("C:\Users\3377\Pictures\Screenshots\屏幕截图 2023-07-28 142455.png")
话说我连样例都过不了……

#include <iostream>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;

const int MAX = 4*1e2+5;

int n, m, x, cnt[MAX*MAX], ans=0, MAXV = INT_MIN;
int step[MAX][MAX];
char g[MAX][MAX];

struct State {
    int x, y;
};

int dx[] = {+1, -1, 0, 0, +1, -1, +1, -1};
int dy[] = {0, 0, +1, -1, +1, -1, -1, +1};


bool inside(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

int bfs(int x1, int y1__) {
    int res = 1;
    queue<State> que;
    step[x1][y1__] = 0;
    que.push(State{x1, y1__});
    while (!que.empty()) {
        State s = que.front();
        que.pop();
        for (int d = 0; d < 8; d++) {
            int x = s.x + dx[d], y = s.y + dy[d];
            if (!inside(x, y) || step[x][y] != -1 || g[x][y] != '*') continue;
            step[x][y] = step[s.x][s.y] + 1;
            que.push(State{x, y});
            res++;
        }
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }

    memset(step, -1, sizeof(step));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == '*' && step[i][j] == -1) {
                x = bfs(i, j);
                cout << x << endl;
                if (x) {
                    cnt[x]++;
                    if (cnt[x] == 2) {
                        ans++;
                    }
                    MAXV = max(MAXV, cnt[x]);
                }
            }
        }
    }

    cout << ans << " " << MAXV;
    return 0;
}
2023/7/28 14:27
加载中...