hdu 4414杭州ネット試合

図を与えて、図の中で‘#’が何個の十字架を構成したかを要求して、十字架の幅が奇数であることに注意して、試合の時チームメートdfsが過ぎたが、私はこのようにするのも速い.
考え方:「#」ごとに判断し、上下左右、歩幅は1、2、..25の中はすべて条件に合っているかどうか、合っているなら個数が奇数であるかどうかを判断すればいい.

#include<iostream>
#include<algorithm>

const int maxn=55;
char map[maxn][maxn];
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
int n;

bool ok(int x,int y){
	return x>=0&&x<n&&y>=0&&y<n;
}

bool check(int x,int y){
	int cnt=0;
	for(int i=1;i<=25;i++){
		int tmpc=0;
		for(int j=0;j<4;j++){

			int xx=x+dx[j]*i,yy=y+dy[j]*i;

			if(ok(xx,yy) && map[xx][yy]=='#'){
				tmpc++;
				if(j%2==0){
					if(yy>0&&map[xx][yy-1]=='#' || yy<n-1&&map[xx][yy+1]=='#')return false;
					cnt++;
				}
				else {
					if(xx>0&&map[xx-1][yy]=='#' || xx<n-1&&map[xx+1][yy]=='#')return false;
					cnt++;
				}
			}
		}
		if(tmpc==0)break;
		if(tmpc!=4)return false;
	}
	if(cnt%2==0&&cnt>0)return true;
	else return false;
}

int main(){
	while(scanf("%d",&n)&&n){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++)scanf(" %c",&map[i][j]);
		}

		int ans=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(map[i][j]=='#' && check(i,j))ans++;
			}
		}


		printf("%d
",ans);

	}
}