Codeforces 11 C. How Many Squares?
問題
0または1からなるグリッドが与えられる。
この中に2x2以上の正方形で、軸に平行または、軸から45度傾いているものはいくつあるか。
ただし、他の1と(8方向のどれかで)隣接しているようなものは正方形とはみなさない。
制約条件
ひとつのテストケース内のグリッドの個数≦10000
グリッドの幅、高さ≦250
方針
1を塗りつぶすのと同時に、x,yの最小値および最大値、x+y,x-yの最小値および最大値をそれぞれ調べる。
座標の最小値、最大値が定まれば、正方形が一意に定まるので、
それにあわせた正方形が実際に描かれているかを調べればいい。
ソースコード
int mx,my,MX,MY,mk,MK,ml,ML,cnt; int n,h,w; string in[250]; void rec(int y,int x){ in[y][x]='2'; cnt++; mx=min(mx,x); MX=max(MX,x); my=min(my,y); MY=max(MY,y); mk=min(mk,y+x); MK=max(MK,y+x); ml=min(ml,y-x); ML=max(ML,y-x); for(int dy=-1;dy<2;dy++)for(int dx=-1;dx<2;dx++)if(dy||dx){ int ny=y+dy,nx=x+dx; if(ny<0||nx<0||ny>=h||nx>=w||in[ny][nx]!='1')continue; rec(ny,nx); } } bool ck1(){ if(MY-my!=MX-mx||cnt!=(MX-mx)*4)return 0; for(int i=my;i<=MY;i++)if(in[i][mx]!='2'||in[i][MX]!='2')return 0; for(int i=mx;i<=MX;i++)if(in[my][i]!='2'||in[MY][i]!='2')return 0; return 1; } bool ck2(){ if(MK-mk!=ML-ml||(ML+mk)%2||(MK-mk)%2||cnt!=(MK-mk)*2)return 0; int y=(ML+mk)/2, x=(mk-ML)/2; const int dy[]={1,-1,-1,1},dx[]={1,1,-1,-1}; rep(d,4){ rep(i,(MK-mk)/2){ if(y<0||x<0||y>=h||x>=w||in[y][x]!='2')return 0; y+=dy[d]; x+=dx[d]; } } return 1; } void run() { cin>>n; while(n--){ cin>>h>>w; rep(i,h)cin>>in[i]; int ans=0; rep(i,h)rep(j,w)if(in[i][j]=='1'){ mx=MX=j; my=MY=i; mk=MK=i+j; ml=ML=i-j; cnt=0; rec(i,j); if(ck1()||ck2())ans++; } cout<<ans<<endl; } }