http://acm.hdu.edu.cn/showproblem.php?pid=1045
#include<iostream> #include<cstring> using namespace std; char map[10][10]; int max1,n; int ju(int i,int j) { if(map[i][j]!='.') return 0; int k; for(k=i-1;k>=1;k--) { if(map[k][j]=='O') return 0; if(map[k][j]=='X') break; } for(k=j-1;k>=1;k--) { if(map[i][k]=='O') return 0; if(map[i][k]=='X') break; } return 1; } void dfs(int i,int k) { int x,y; if(i==n*n) { max1=max1>k?max1:k; return; } x=i/n+1; y=i%n+1; if(ju(x,y)) { map[x][y]='O'; dfs(i+1,k+1); map[x][y]='.'; } dfs(i+1,k); } int main() { while(cin>>n,n!=0) { memset(map,0,sizeof(map)); int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) cin>>map[i][j]; max1=0; dfs(0,0); cout<<max1<<endl; } }