PKU 1974 The Happy Worm
http://poj.org/problem?id=1974
m*nの長方形の空間にk個の石がある。
この時、ある芋虫は縦又は横に可能な限り伸び切るように横たわる。
芋虫は石のあるマスや、長方形の外以外は伸びることが出来る時、何通りの芋虫の配置があるかを答えろというような問題。
半月ぶりのPKU。
入力がかなり多いようなので、vectorとかを使って結構TLEをもらいました。
石の座標と番兵をpair
PI in[1000000]; void solv(){ int m,n,k; scanf("%d%d%d",&m,&n,&k); rep(i,k){ int x,y; scanf("%d%d",&x,&y); --x,--y; in[i]=mp(x,y); } int ans=0; rep(i,m){ in[k+2*i]=mp(i,-1); in[k+2*i+1]=mp(i,n); } rep(i,n){ in[k+2*m+2*i]=mp(-1,i); in[k+2*m+2*i+1]=mp(m,i); } rep(t,2){ sort(in,in+2*m+2*n+k); rep(i,2*m+2*n+k-1){ if(in[i].F==in[i+1].F && in[i].S+2<in[i+1].S)++ans; swap(in[i].F,in[i].S); } swap(in[2*m+2*n+k-1].F,in[2*m+2*n+k-1].S); } printf("%d\n",ans); } main(){ int t; scanf("%d",&t); rep(i,t)solv(); }