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;
	}
}