Posted on 2008-03-12 09:21
superman 閱讀(834)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1002 C++ 00:00.01 840K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, best;
7 char map[5][5];
8
9 bool canPut(int x, int y)
10 {
11 if(map[x][y] != '.')
12 return false;
13 for(int i = x - 1; i >= 0; i--)
14 {
15 if(map[i][y] == 'X') break;
16 if(map[i][y] == 'O') return false;
17 }
18 for(int i = x + 1; i < n; i++)
19 {
20 if(map[i][y] == 'X') break;
21 if(map[i][y] == 'O') return false;
22 }
23 for(int j = y - 1; j >= 0; j--)
24 {
25 if(map[x][j] == 'X') break;
26 if(map[x][j] == 'O') return false;
27 }
28 for(int j = y + 1; j < n; j++)
29 {
30 if(map[x][y] == 'X') break;
31 if(map[x][j] == 'O') return false;
32 }
33 return true;
34 }
35
36 bool donePut()
37 {
38 for(int i = 0; i < n; i++)
39 for(int j = 0; j < n; j++)
40 if(canPut(i, j))
41 return false;
42 return true;
43 }
44
45 void search(int m)
46 {
47 if(donePut())
48 {
49 best >?= m;
50 return;
51 }
52 for(int i = 0; i < n; i++)
53 for(int j = 0; j < n; j++)
54 if(canPut(i, j))
55 {
56 map[i][j] = 'O';
57 search(m + 1);
58 map[i][j] = '.';
59 }
60 }
61
62 int main()
63 {
64 while((cin >> n) && n)
65 {
66 for(int i = 0; i < n; i++)
67 for(int j = 0; j < n; j++)
68 switch(cin.get())
69 {
70 case '.' : map[i][j] = '.'; break;
71 case 'X' : map[i][j] = 'X'; break;
72 default : j--;
73 }
74 best = 0;
75 search(0);
76 cout << best << endl;
77 }
78
79 return 0;
80 }
81