AOJ 1337 Count the Regions
いもす法を排他的論理和でやるみたいな方法で解きました。
長方形に番号をふります。
グリッドのマスの、2進数のある桁が1になっているとき、そのマスには(その桁数)番の長方形が存在する、という風に対応させます。
いもす法みたいに配置して累積XORをとるとうまくできます。
累積XORを使うとbit分の長方形を同時に扱うことができるので、定数倍高速化されます。うれしい
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define IDX(x,v) distance(v,lower_bound(v,(v)+2*N,x)) #define fs first #define sn second typedef long long ll; typedef pair<int, int> P; typedef pair<P, P> R; int N; R rec[50]; int X[100], Y[100]; ll a[103][103]; const int dx[] = {0,0,-1,1}; const int dy[] = {-1,1,0,0}; void dfs(ll b, int y, int x){ a[y][x] = -1; for(int i=0; i<4; i++){ int ny = y+dy[i]; int nx = x+dx[i]; if(0<=ny&&ny<=2*N+1 && 0<=nx&&nx<=2*N+1 && a[ny][nx]==b) dfs(b,ny,nx); } } int main(){ while(scanf("%d",&N) && N!=0){ memset(a,0,sizeof(ll)*103*103); for(int i = 0; i < N; i++){ int l, t, r, b; scanf("%d %d %d %d",&l,&t,&r,&b); X[2*i]=l; X[2*i+1]=r; Y[2*i]=t; Y[2*i+1]=b; rec[i] = R(P(l,t),P(r,b)); } sort(X,X+2*N); sort(Y,Y+2*N); for(int i = 0; i < N; i++){ int l = IDX(rec[i].fs.fs,X); int t = IDX(rec[i].fs.sn,Y); int r = IDX(rec[i].sn.fs,X); int b = IDX(rec[i].sn.sn,Y); a[t+1][l+1] += (1L)<<i; a[t+1][r+1] += (1L)<<i; a[b+1][l+1] += (1L)<<i; a[b+1][r+1] += (1L)<<i; } for(int i = 1; i <= 2*N+1; i++) for(int j = 1; j <= 2*N+1; j++) a[i][j] = a[i][j-1]^a[i][j]; for(int j = 1; j <= 2*N+1; j++) for(int i = 1; i <= 2*N+1; i++) a[i][j] = a[i-1][j]^a[i][j]; int ans = 0; for(int i = 0; i<=2*N+1; i++){ for(int j = 0; j<=2*N+1; j++){ if(a[i][j] >= 0){ dfs(a[i][j],i,j); ans++; } } } printf("%d\n", ans); } }