AOJ0531 Paint Color

実質初投稿です。
AOJのsolved数は現在141。今はJOI予選までにVol5全完を目標にしています。

解法

W,Hの値が大きいので座標圧縮をする。
それはすぐわかるのだけど、実装しながら大量のバグを埋め込んだせいでいままでずっと解けていなかった問題。
長方形の領域を塗るので、2次元imos法を使う。最後に領域を数えるためにBFSかDFSをする。
DFSだとスタックオーバーフローが怖いのでBFSしました。
(DFSでも大丈夫だし、imos法を使わなくても間に合うらしい。)
座標を配列で表す時はx,yが反対であることに注意。（自分はいつも間違える…）

ソースコード

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
int X1[1005],X2[1005],Y1[1005],Y2[1005];
int f[3030][3030];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int W,H,N;
int ans=0;
int compress(int* x1,int* x2,int t)
{
    vector<int> xs;
    for(int i=0;i<N;i++)
    {
        int tx1=x1[i],tx2=x2[i];
        if(1<=tx1&&tx1<t)xs.pb(tx1);
        if(1<=tx2&&tx2<t)xs.pb(tx2);
    }
    xs.pb(0);xs.pb(t);
    SORT(xs);
    xs.erase(unique(all(xs)),xs.end());
    for(int i=0;i<N;i++)
    {
        x1[i]=find(all(xs),x1[i])-xs.begin();
        x2[i]=find(all(xs),x2[i])-xs.begin();
    }
    return xs.size()-1;
}
int main()
{
    while(1)
    {
        memset(f,0,sizeof(f));
        ans=0;
        cin >> W >> H;
        if(W==0&&H==0)return 0;
        cin >> N;
        for(int i=0;i<N;i++)
        {
            cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
        }
        W=compress(X1,X2,W);
        H=compress(Y1,Y2,H);
        for(int i=0;i<N;i++)
        {
            f[Y1[i]][X1[i]]++;
            f[Y2[i]][X2[i]]++;
            f[Y1[i]][X2[i]]--;
            f[Y2[i]][X1[i]]--;
        }
        for(int i=0;i<H;i++)
        {
            for(int j=1;j<W;j++)
            {
                f[i][j]+=f[i][j-1];
            }
        }
        for(int i=1;i<H;i++)
        {
            for(int j=0;j<W;j++)
            {
                f[i][j]+=f[i-1][j];
            }
        }
        for(int i=0;i<H;i++)
        {
            for(int j=0;j<W;j++)
            {
                if(f[i][j])continue;
                ans++;
                queue<P> q;
                q.push(mp(j,i));
                while(!q.empty())
                {
                    int tx=q.front().fi,ty=q.front().sec;
                    q.pop();
                    for(int k=0;k<4;k++)
                    {
                        int ttx=tx+dx[k],tty=ty+dy[k];
                        if(ttx<0||ttx>W||tty<0||tty>H||f[tty][ttx]>0)continue;
                        q.push(mp(ttx,tty));
                        f[tty][ttx]=1;
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}