PKU 1315 Don't Get Rooked (ZOJ 1002 Fire Net)
http://poj.org/problem?id=1315
nクイーン問題に似たような問題。
dfs
string in[4]; int n,ans; void dfs(int pos,int tans){ ans=max(ans,tans); if(pos==n*n){ ans=max(ans,tans); return; } for(int i=pos;i<n*n;i++){ int x=i/n,y=i%n; if(in[x][y]!='.')continue; bool ok=true; rep(j,4){ int cx=x,cy=y; while(0<=cx && cx<n && 0<=cy && cy<n && in[cx][cy]!='X'){ if(in[cx][cy]=='x')ok=false; cx+=dx[j]; cy+=dy[j]; } } if(!ok)continue; in[x][y]='x'; dfs(i+1,tans+1); in[x][y]='.'; } } main(){ while(cin>>n,n){ rep(i,n)cin>>in[i]; ans=0; dfs(0,0); cout<<ans<<endl; } }
4/16追記
ZOJの1002が全く同じ問題みたいですね。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2