영역 구하기

#include<iostream>
#include<utility>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int n, m, k;

int a[101][101];
bool d[101][101];
vector<pair<int, int>> rect[101];

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


void bfs(int xx, int yy, vector<int>& v){
    queue<pair<int, int>> q;
    q.push(make_pair(yy, xx));
    d[yy][xx] = true;
    a[yy][xx] = 1;
    int result = 1;
    while(!q.empty()){
        int x = q.front().second; int y = q.front().first;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x+dx[i]; int ny = y+dy[i];
            if(nx>= 0 && nx < n && ny >= 0 && ny < m){
                if(d[ny][nx] == false){
                    if(a[ny][nx] == 0){
                        result += 1;
                        a[ny][nx] = 1;
                        d[ny][nx] = true;
                        q.push(make_pair(ny,nx));
                    }
                }
            }
        }
    }
    if(result )
    v.push_back(result);
}

void filling(int x1,int y1, int x2, int y2){
    for(int i = y1; i < y2; i++){
        for(int j = x1; j < x2; j++){
            a[i][j] = -1;
            d[i][j] = true;
        }
    }

}

void make_rect(){
    for(int i = 0; i < k; i++){
        int x1 = rect[i][0].first;
        int y1 = rect[i][0].second;
        int x2= rect[i][1].first;
        int y2 = rect[i][1].second;
        filling(x1,y1,x2,y2);
    }
}


int main(){
    scanf("%d %d %d", &m, &n, &k);

    for(int i = 0; i < k; i++){
        for(int j = 0; j < 2; j++){
            int x, y;
            scanf("%d %d", &x, &y);
            rect[i].push_back(make_pair(x,y));
        }
    }
    make_rect();

    int sum = 0;
    vector<int> toss;
    for(int i = 0;  i < m; i++){
        for(int j = 0; j < n; j++){
            if(d[i][j] == false && a[i][j] == 0){
                sum += 1;
                a[i][j] =1;
                d[i][j] = true;
                bfs(j,i,toss);
            }
        }
    }
    cout<<sum<<endl;
    sort(toss.begin(), toss.end());
    for(int i = 0; i < toss.size(); i++){
        cout<<toss[i]<<" ";
    }
    cout<<endl;



    return 0;
}

채우고 -> 벡터로 BFS 하고 -> 다시 채우고 반복해서하기, 사실상 BFS형 브루트포스인듯