간단한 탐색문제

2583_영역 구하기

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int m,n,k;
bool map[101][101];
queue<pair<int, int>> qu;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
vector<int> vec;
int main(){
    cin>>m>>n>>k;
    for(int i=0; i<k; i++) {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        for(int t=m-d; t<m-b; t++) {
            for(int j=a; j<c; j++) {
                map[t][j]=true;
            }
        }
    }
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(!map[i][j]) {
                map[i][j]=true;
                qu.push({i,j});
                int cnt=0;
                while(!qu.empty()) {
                    pair<int, int> temp = qu.front();
                    qu.pop();
                    cnt++;
                    for(int s=0; s<4; s++) {
                        int curi = temp.first + dx[s];
                        int curj = temp.second + dy[s];
                        if(curi>=0 && curi<m && curj>=0 && curj<n && !map[curi][curj]) {
                            qu.push({curi,curj});
                            map[curi][curj]=true;
                        }
                    }
                }
                vec.push_back(cnt);
            }
        }
    }
    sort(vec.begin(), vec.end());
    cout<<vec.size()<<endl;
    for(int i=0; i<vec.size(); i++)
        cout<<vec[i]<<" ";
    cout<<endl;
}