[BOJ 2583] 영역 구하기

문제에서 표시된 영역만 잘 그려주면 됨. 일반적으로 i,j 순서대로 돌면서 체크하면 다르게 나오고, (0,0)의 위치가 우리가 평소에 쓰는 위치랑 다르기 때문에 x 좌표를 다르게 해놓고 움직여야한다.

그리고 다 그려주면 영역이 '0' 인 곳만 체크해주면서 개수를 세주면 된다

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef pair<int, int> pii;
bool vis[101][101];
int M, N, K, a[101][101], xx1, yy1, xx2, yy2;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
vector<int> ret;
int cnt;

bool inrange(int nx, int ny) {
    if(nx < 0 || nx >= M || ny < 0 || ny >= N) return false;
    return true;
}
int main() {
    cin >> M >> N >> K;
    while(K--) {
        cin >> xx1 >> yy1 >> xx2 >> yy2;
        for(int i = M - yy2; i <= M - yy1 - 1; i++) 
            for(int j =xx1; j <= xx2 - 1; j++) 
                a[i][j] = 1;
    } 
    queue<pii> q;
    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
            if(!vis[i][j] && !a[i][j]) {
                int ans = 1;
                cnt++;
                q.push({i, j}); vis[i][j] = true;
                while(!q.empty()) {
                    auto cur = q.front(); q.pop();
                    for(int dir = 0; dir < 4; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if(vis[nx][ny]) continue;
                        if(!inrange(nx, ny)) continue;
                        if(a[nx][ny]) continue;
                        q.push({nx, ny}); vis[nx][ny] = true;
                        ans++;
                    }
                }
                ret.push_back(ans);
            }
        }
    }
    sort(ret.begin(), ret.end());
    cout << cnt << '\n';
    for(int i = 0 ; i < ret.size(); i++)
        cout << ret[i] << ' '; 
}