2583 영역 구하기

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

DFS로 연결 요소의 개수를 세준다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int m,n,k,a,b,c,d,sum,map[101][101];
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
vector<int> v;
 
void dfs(int x,int y)
{
    sum++,map[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0 || nx>=m || ny<0 || ny>=n) continue;
        if(!map[nx][ny]) dfs(nx,ny);
    }
}
 
int main()
{
    scanf("%d %d %d",&m,&n,&k);
    while(k--)
    {
        scanf("%d %d %d %d",&a,&b,&c,&d);
        for(int i=b;i<d;i++) for(int j=a;j<c;j++)
            map[i][j]=1;
    }
    for(int i=0;i<m;i++) for(int j=0;j<n;j++)
        if(!map[i][j]) sum=0,dfs(i,j),v.push_back(sum);
    k=v.size();
    sort(v.begin(),v.end());
    printf("%d\n",k);
    for(int i=0;i<k;i++) printf("%d ",v[i]);
    return 0;
}