ACM-ICPC Regionals 2013 >> Asia - Aizu - Count the Regions

Hash处理，多水

const int maxn=210;//这里因为错写成110而RE了一次
const int inf=99999999;
const double eps=1e-3;

vector<int> vx,vy;
map<int,int> hx,hy;
bool vis[maxn][maxn];

struct Poly
{
    int x1,y1,x2,y2;
} Pl[maxn];

void dfs(int n,int x,int y)
{
    if (x<0||y<0||x>n||y>n) return ;
    if (!vis[x][ y ])
    {
        vis[x][ y ]=1;
        dfs(n,x-1,y);
        dfs(n,x+1,y);
        dfs(n,x,y-1);
        dfs(n,x,y+1);
    }
}

int main()
{
    int n=1;
    while(~scanf("%d",&n))
    {
        if (!n) break;
        vx.clear();vy.clear();
        hx.clear();hy.clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&Pl[i].x1,&Pl[i].y1,&Pl[i].x2,&Pl[i].y2);
            vx.push_back(Pl[i].x1);vx.push_back(Pl[i].x2);
            vy.push_back(Pl[i].y1);vy.push_back(Pl[i].y2);
        }
        sort(vx.begin(),vx.end());
        sort(vy.begin(),vy.end());
        //cout<<vx.size()<<' '<<vy.size()<<endl;
        for(int i=0;i<vx.size();i++) hx[vx[i]]=2*i+1;
        for(int i=0;i<vy.size();i++) hy[vy[i]]=2*i+1;
//cout<<"--"<<endl;
        CLEAR(vis);
        for(int i=1;i<=n;i++)
        {
            int x1=hx[Pl[i].x1];
            int x2=hx[Pl[i].x2];
            if (x1>x2) swap(x1,x2);
            int y1=hy[Pl[i].y1];
            int y2=hy[Pl[i].y2];
            if (y1>y2) swap(y1,y2);
            //cout<<hx[Pl[i].x1]<<' '<<hy[Pl[i].y1]<<' '<<hx[Pl[i].x2]<<' '<<hy[Pl[i].y2]<<endl;
            for(int j=x1;j<=x2;j++) vis[j][y1]=vis[j][y2]=1;
            for(int j=y1;j<=y2;j++) vis[x1][j]=vis[x2][j]=1;
        }
        int ans=0;
        for(int i=0;i<=4*n;i++)
        {
            //for(int j=0;j<=4*n;j++)cout<<vis[i][j]<<' ';cout<<endl;
            for(int j=0;j<=4*n;j++)
                if (!vis[i][j])
                {
                    ans++;
                    dfs(4*n,i,j);
                }
        }
        cout<<ans<<endl;
    }
    return 0;
}