PKU 2458 Rigging the Bovine Election

http://poj.org/problem?id=2458
5*5のマスにHolsteinとJerseyのどちらかが配置されている。
この中から縦と横につながっている7マスを選択してHolsteinの数よりJerseysの方が多くなるような選び方が何通りあるかを答えろというような問題。

dfsで全探索。
こういう感じの適度な実装の全探索は結構好きです。

string in[5];
int ans;
set<int> app;
void dfs(int v,int st,int J){
  if(J+7-v<4)return;  
  if(app.count(st))return;
  app.insert(st);  
  if(v==7){
    ++ans;
    return;
  }

  rep(i,25){
    if(st&(1<<i))continue;
    int x=i/5,y=i%5;
    bool ok=false;
    rep(j,4){
      int nx=x+dx[j],ny=y+dy[j];
      if(0>nx || nx>4 ||
         0>ny || ny>4 ||
         (st&(1<<nx*5+ny))==0)continue;
      ok=true;
      break;
    }
    if(!ok)continue;
    dfs(v+1,st|1<<i,J+(in[x][y]=='J'));
  }
}

main(){
  rep(i,5)cin>>in[i];
  rep(i,25)dfs(1,1<<i,in[i/5][i%5]=='J');
  cout<<ans<<endl;
}