2583 : 영역 구하기

풀이

직사각형 영역에 체크를 해놓고

모든 칸을 돌면서 bfs나 dfs나 아무거나 돌려주면 된다.

입력이 좀 짜증난다 (…)

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

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

int n, m, k, cnt, a[111][111];
vector<int> v;

int dfs(int x, int y) {
    int ret = 1;
    a[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (!a[nx][ny]) ret += dfs(nx, ny);
    }
    return ret;
}

int main() {
    scanf("%d %d %d", &n, &m, &k);
    while (k--) {
        int e, b, c, d;
        scanf("%d %d %d %d", &e, &b, &c, &d);
        for (int i = b; i < d; i++)
            for (int j = e; j < c; j++)
                a[i][j] = 1;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (!a[i][j]) v.push_back(dfs(i, j));

    sort(v.begin(), v.end());
    printf("%d\n", v.size());
    for (auto now : v) printf("%d ", now);

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-05-22 17:23

Read more posts by this author