- 概要
日本語の問題なので省略させて頂きます。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531
- 解法
幅 w (1 ≤ w ≤ 1000000 となる整数) と高さ h (1 ≤ h ≤ 1000000 となる整数)
とあるので当然普通にやったら要素数が足りません。
座標圧縮 をします。
座標圧縮については蟻本やJOIの解説を見るとわかりやすいです。
圧縮したあとはBFSで各座標について調べることで少ないオーダーで済ませることができます。
座標圧縮についてスライド作ろうとか思ったけど
より詳しい人に突っ込まれたくないのでやめておく(誰かお願いします
#include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<queue> #include<map> #define MAX_N 1000 using namespace std; typedef pair<int,int> P; int n; bool f[2*MAX_N+6][2*MAX_N+6]; int cp(int *z1,int *z2,int k) { vector<int> xs; for(int i=0;i<n;i++){ xs.push_back(z1[i]); if(z1[i]-1>=0)xs.push_back(z1[i]-1); xs.push_back(z2[i]-1); if(z2[i]<k)xs.push_back(z2[i]); } sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end()); for(int i=0;i<n;i++){ z1[i]=find(xs.begin(),xs.end(),z1[i])-xs.begin(); z2[i]=find(xs.begin(),xs.end(),z2[i])-xs.begin(); } return xs.size(); } int main() { int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int w,h; while(scanf("%d%d",&w,&h),w||h){ scanf("%d",&n); int x1[MAX_N+1],x2[MAX_N+1],y1[MAX_N+1],y2[MAX_N+1]; for(int i=0;i<n;i++){ scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]); } w=cp(x1,x2,w); h=cp(y1,y2,h); memset(f,0,sizeof(f)); for(int i=0;i<n;i++){ for(int x=x1[i];x<x2[i];x++){ for(int y=y1[i];y<y2[i];y++){ f[x][y]=true; } } } int ans=0; for(int i=0;i<w;i++){ for(int j=0;j<h;j++){ if(f[i][j])continue; ans++; queue<P> q; q.push(make_pair(i,j)); f[i][j]=true; while(!q.empty()){ int x=q.front().first,y=q.front().second; q.pop(); for(int l=0;l<4;l++){ int xx=x+dx[l],yy=y+dy[l]; if(xx<0 || xx>=w || yy<0 || yy>=h)continue; if(!f[xx][yy]){ q.push(make_pair(xx,yy)); f[xx][yy]=true; } } } } } printf("%d\n",ans); } return 0; }
JOI本選進出者が発表されました。
自分もいますので、探してください。