http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2
#include <iostream> using namespace std; char map[5][5]; bool CanPut(char map[5][5],int x,int y) { if (map[x][y]!='.') return false; for (int i=x-1;i>=0;--i) { if (map[i][y]=='F') return false; if (map[i][y]=='X') break; } for (int i=y-1;i>=0;--i) { if (map[x][i]=='F') return false; if (map[x][i]=='X') break; } return true; } void DFS(char map[5][5],int const N,int const step,int const put,int &max) { if (max<put) max = put; if (step>=N*N) return; int x = step/N; int y = step%N; if (CanPut(map,x,y)) { map[x][y]='F'; DFS(map,N,step+1,put+1,max); map[x][y]='.'; } DFS(map,N,step+1,put,max); } void ACM1002() { int N; while(cin>>N&&N!=0) { for (int i=0;i<N;++i) cin>>map[i]; int max =0; DFS(map,N,0,0,max); cout<<max<<endl; } } int main() { ACM1002(); return 0; }