2458 Rigging the Bovine Election

問題概要

5x5のグリッドにH,Jが書かれている。
このグリッドの縦または横に連続した大きさ7の部分で、Jの数がHの数より多いものは何通りあるか。

解法

深さ優先探索して全部数えればよい。
一度出現した局面は覚えて二度以上探索しないようにする。
局面は、マスが25しかないので、ビットで表現して整数型に収まる。
（下のコードではうっかりlong longを使ったがintでおｋ）

ソースコード

int ans,dx[]={-1,0,1,0},dy[]={0,-1,0,1};
char in[5][7];
set<ll> S;

void rec(ll s,int H,int J){
	if(S.count(s))return;
	S.insert(s);
	
	if(H+J==7){
		if(H<4)ans++;
		return;
	}
	rep(i,5)rep(j,5)if(s&1<<i*5+j)rep(d,4)
	{
		int y=i+dy[d],x=j+dx[d],nh=H,nj=J;
		if(y<0||x<0||y>4||x>4)continue;
		if(in[y][x]=='H')nh++; if(in[y][x]=='J')nj++;
		if(nh<4)rec(s|1<<y*5+x,nh,nj);
	}
}
int main(){
	rep(i,5)gets(in[i]);
	rep(i,5)rep(j,5)rec(1<<i*5+j,in[i][j]=='H',in[i][j]=='J');
	printf("%d\n",ans);
	
	return 0;
}