JOI2008本選 問題5@C++(-31)
やっとできたーーーーーーーーーーーっ!
いやこれを本番で解くとか不可能だろ。
どんだけ必死だったかはソース見ればわかるので多くを語らない。コメント付けたから読めると思う。
/* TASKNO: 5 LANG: C++ NAME: Masaki Hara J */ #include <cstdio> #include <algorithm> #include <queue> #include <vector> //座標圧縮を行わないオプション //#define NO_COMP //デバッグ用出力のオプション //#define DEBUG_PRINT using namespace std; int main(int argc,char* argv[]) { //ファイルを開く。 FILE* in=fopen(argc>1?argv[1]:"input.txt","r"); FILE* out=fopen(argc>2?argv[2]:"output.txt","w"); int real_w,real_h,n; fscanf(in,"%d %d\n",&real_w,&real_h); fscanf(in,"%d\n",&n); #ifdef DEBUG_PRINT printf("real_w=%d,real_h=%d,n=%d\n",real_w,real_h,n); #endif //外壁用スペースの確保 real_w+=2; real_h+=2; //座標圧縮用ハッシュ。差分状態で保持して後で和分する。 vector<int> rtov_x(real_w+1); vector<int> rtov_y(real_h+1); //矩形を格納 vector<pair<pair<int,int>,pair<int,int> > > rects(n+4); //使用する座標のrtovを1にする作業 //外壁用の座標を確保 rtov_x[0]++; rtov_y[0]++; rtov_x[1]++; rtov_y[1]++; rtov_x[real_w-1]++; rtov_y[real_h-1]++; rtov_x[real_w]++; rtov_y[real_h]++; //矩形で使用する座標を確保 for(int i=0;i<n;i++) { int& x1=rects[i].first.first; int& y1=rects[i].first.second; int& x2=rects[i].second.first; int& y2=rects[i].second.second; fscanf(in,"%d %d %d %d\n",&x1,&y1,&x2,&y2); x1++;y1++;x2++;y2++; if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); if(rtov_x[x1]==0) rtov_x[x1]++; if(rtov_x[x2]==0) rtov_x[x2]++; if(rtov_y[y1]==0) rtov_y[y1]++; if(rtov_y[y2]==0) rtov_y[y2]++; } #ifdef NO_COMP for(int x=0;x<real_w+1;x++) {rtov_x[x]=x;}int width=real_w; for(int y=0;y<real_h+1;y++) {rtov_y[y]=y;}int height=real_h; #else /* NO_COMP */ //rtovを和分することで、座標ハッシュとして機能させる //例 //1,1,0,1,1,0,0,0,0,0,0,1,1, から //0,1,1,2,3,3,3,3,3,3,3,4,5, にする //virtual_x = rtov_x[real_x] となる int subsum=0; for(int x=0;x<real_w+1;x++) {subsum+=rtov_x[x];rtov_x[x]=subsum-1;}int width=subsum-1; subsum=0; for(int y=0;y<real_h+1;y++) {subsum+=rtov_y[y];rtov_y[y]=subsum-1;}int height=subsum-1; #endif /* NO_COMP */ #ifdef DEBUG_PRINT for(int x=0;x<real_w+1;x++) {printf("%d,",rtov_x[x]);}printf("\n"); for(int y=0;y<real_h+1;y++) {printf("%d,",rtov_y[y]);}printf("\n"); printf("width=%d,height=%d\n",width,height); #endif /* DEBUG_PRINT */ //マスキングテープの枚数を表すマップ。 //こちらも、差分状態で作成して、あとから和分する vector<vector<int> > paper_map(width+1,vector<int>(height+1)); for(int i=0;i<n;i++) { int x1=rtov_x[rects[i].first.first]; int y1=rtov_y[rects[i].first.second]; int x2=rtov_x[rects[i].second.first]; int y2=rtov_y[rects[i].second.second]; #ifdef DEBUG_PRINT printf("%d %d %d %d => %d %d %d %d\n",rects[i].first.first,rects[i].first.second,rects[i].second.first,rects[i].second.second,x1,y1,x2,y2); #endif if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); //このようにすると、和分したときに矩形が現れる paper_map[x1][y1]++; paper_map[x1][y2]--; paper_map[x2][y1]--; paper_map[x2][y2]++; } //外壁の追加。(0,0,width,height)から(1,1,width-1,height-1)を引き算する形。 paper_map[0][0]++; paper_map[0][height]--; paper_map[width][0]--; paper_map[width][height]++; paper_map[1][1]--; paper_map[1][height-1]++; paper_map[width-1][1]++; paper_map[width-1][height-1]--; #ifdef DEBUG_PRINT for(int y=0;y<height+1;y++) { for(int x=0;x<width+1;x++) { printf("%2d ",paper_map[x][y]); } printf("\n"); } #endif /* DEBUG_PRINT */ //x方向に和分。 for(int x=0;x<width+1;x++) { for(int y=0;y<height+1;y++) { if(x>0) paper_map[x][y]+=paper_map[x-1][y]; } } //y方向に和分。 for(int x=0;x<width+1;x++) { for(int y=0;y<height+1;y++) { if(y>0) paper_map[x][y]+=paper_map[x][y-1]; } } #ifdef DEBUG_PRINT printf("\n"); for(int y=0;y<height;y++) { for(int x=0;x<width;x++) { printf("%2d ",paper_map[x][y]); } printf("\n"); } #endif /* DEBUG_PRINT */ //ここでようやく領域の数を数える。 int area_count=0; for(int x=1;x<width-1;x++) { for(int y=1;y<height-1;y++) { if(!paper_map[x][y]) { area_count++; //幅優先探索 queue<pair<int,int> > que; que.push(make_pair(x,y)); while(!que.empty()) { int cx=que.front().first; int cy=que.front().second; que.pop(); if(!paper_map[cx][cy]) { paper_map[cx][cy]++; que.push(make_pair(cx-1,cy)); que.push(make_pair(cx+1,cy)); que.push(make_pair(cx,cy-1)); que.push(make_pair(cx,cy+1)); } } } } } #ifdef DEBUG_PRINT printf("\n"); for(int y=0;y<height;y++) { for(int x=0;x<width;x++) { printf("%2d ",paper_map[x][y]); } printf("\n"); } #endif /* DEBUG_PRINT */ //出力して終了 fprintf(out,"%d\n",area_count); fclose(out); fclose(in); return 0; }