原题:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002
#include<stdio.h> #include<string.h> char maps[5][5]; int n,ans; int judge(int x,int y) { int temp; if(maps[x][y] == 'X' || maps[x][y] == 'C')return 0; for(temp=y-1;temp>=1;temp--) { if(maps[x][temp] == 'X')break; else if(maps[x][temp] == 'C')return 0; } for(temp=y+1;temp<=n;temp++) { if(maps[x][temp] == 'X')break; else if(maps[x][temp] == 'C')return 0; } for(temp=x-1;temp>=1;temp--) { if(maps[temp][y] == 'X')break; else if(maps[temp][y] == 'C')return 0; } for(temp=x+1;temp<=n;temp++) { if(maps[temp][y] == 'X')break; else if(maps[temp][y] == 'C')return 0; } return 1; } void dfs(int k) { int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(judge(i,j)) { maps[i][j] = 'C'; dfs(k+1); maps[i][j] = '.'; } } } ans = ans>k?ans:k; } int main() { int i,j; while(1) { scanf("%d",&n); if(n == 0)break; scanf("\n"); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) scanf("%c",&maps[i][j]); if(i<n) scanf("\n"); } ans = 0; dfs(0); printf("%d\n",ans); } return 0; }