Paint Color

Paint Color

该题关键就在于坐标离散化,然后要注意的一点就是把点坐标表示为每一个格子的坐标。

// Created by CAD on 2020/2/4.
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;

const int maxn=1005;
int compress(int *a,int *b,int w,int n){
    vector<int> v;
    for(int i=1;i<=n;++i){
        for(int d=-1;d<=1;++d)
        {
            int ta=a[i]+d,tb=b[i]+d;
            if(1<=ta&&ta<=w) v.push_back(ta);
            if(1<=tb&&tb<=w) v.push_back(tb);
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;++i)
    {
        a[i]=find(v.begin(),v.end(),a[i])-v.begin()+1;
        b[i]=find(v.begin(),v.end(),b[i])-v.begin()+1;
    }
    return v.size();
}
bool g[maxn*6][maxn*6];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int w,h,n;
    while(cin>>w>>h&&w&&h){
        cin>>n;
        int x1[maxn],x2[maxn],y1[maxn],y2[maxn];
        for(int i=1;i<=n;++i)
            cin>>x1[i]>>y1[i]>>x2[i]>>y2[i],x1[i]++,y1[i]++;
        w=compress(x1,x2,w,n),h=compress(y1,y2,h,n);
        for(int i=1;i<=w;++i)
            for(int j=1;j<=h;++j)
                g[i][j]=0;
        for(int i=1;i<=n;++i)
            for(int x=x1[i];x<=x2[i];++x)
                for(int y=y1[i];y<=y2[i];++y)
                    g[x][y]=1;
        int ans=0;
        int dx[4]={0,0,1,-1};
        int dy[4]={1,-1,0,0};
        for(int x=1;x<=w;++x)
            for(int y=1;y<=h;++y)
                if(!g[x][y]){
                    ans++;
                    queue<pii> q;
                    q.push({x,y});
                    while(!q.empty()){
                        pii now=q.front();q.pop();
                        for(int i=0;i<4;++i){
                            int tx=now.fi+dx[i],ty=now.se+dy[i];
                            if(tx<1||tx>w||ty<1||ty>h||g[tx][ty]) continue;
                            q.push({tx,ty}),g[tx][ty]=1;
                        }
                    }
                }
        cout<<ans<<'\n';
    }
    return 0;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。