2583번: 영역 구하기

https://www.acmicpc.net/problem/2583


$O(nm+k)$

#include<cstdio>
#include<algorithm>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int a[100][100], m, n, c, r[10000], rcnt;
void f(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m || a[x][y]) return;
    a[x][y] = 1;
    r[rcnt]++;
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d %d %d", &m, &n, &c);
    for (int i = 0, x, y, z, w; i < c; i++) {
        scanf("%d %d %d %d", &x, &y, &z, &w);
        for (int j = x; j < z; j++) for (int k = y; k < w; k++) a[j][k] = 1;
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (!a[i][j]) f(i, j), rcnt++;
    std::sort(r, r + rcnt);
    printf("%d\n", rcnt);
    for (int i = 0; i < rcnt; i++) printf("%d ", r[i]);
    return 0;
}