Posted on 2009-03-24 20:44
superman 阅读(97)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 bool C[50], A[50], B[50];
6 bool * x = C + 25, * LR = A + 25, * RL = B + 25;
7
8 int n;
9 int cnt;
10
11 void search(int i, int pos[])
12 {
13 if (cnt == 3)
14 return;
15 if (i == n)
16 {
17 cnt++;
18 for (int k = 0; k < n; k++)
19 cout << pos[k] + 1 << (k == n - 1 ? '\n' : ' ');
20 return;
21 }
22
23 for (int j = 0; j < n; j++)
24 if (x[j] == false)
25 {
26 pos[i] = j;
27
28 int k;
29 for (k = 0; k < i; k++)
30 if (abs(i - k) == abs(pos[i] - pos[k]))
31 break;
32
33 if (k == i)
34 {
35 x[j] = true;
36
37 search(i + 1, pos);
38
39 x[j] = false;
40 }
41 }
42 }
43
44 void search_odd(int i, const int x0, const int x1)
45 {
46 if (i == n)
47 {
48 if (x0 == x1)
49 cnt += 1;
50 else
51 cnt += 8;
52 return;
53 }
54 if (i == x0 || i == x1)
55 {
56 search_odd(i + 1, x0, x1);
57 return;
58 }
59 for (int j = 0; j < n; j++)
60 if (x[j] || LR[i - j] || RL[i + j])
61 ;
62 else
63 {
64 x[j] = LR[i - j] = RL[i + j] = true;
65
66 search_odd(i + 1, x0, x1);
67
68 x[j] = LR[i - j] = RL[i + j] = false;
69 }
70 }
71
72 void search_even(int i)
73 {
74 if (i == n)
75 {
76 cnt += 2;
77 return;
78 }
79
80 int t = (i ? n : n / 2);
81 for (int j = 0; j < t; j++)
82 if (x[j] || LR[i - j] || RL[i + j])
83 ;
84 else
85 {
86 x[j] = LR[i - j] = RL[i + j] = true;
87
88 search_even(i + 1);
89
90 x[j] = LR[i - j] = RL[i + j] = false;
91 }
92 }
93
94 int main()
95 {
96 freopen("checker.in", "r", stdin);
97 freopen("checker.out", "w", stdout);
98
99 cin >> n;
100
101 int pos[13];
102 search(0, pos);
103
104 for (int i = -n + 1; i < n; i++)
105 LR[i] = false;
106 for (int i = 0; i <= 2 * n - 2; i++)
107 RL[i] = false;
108
109 cnt = 0;
110 if (n % 2 == 0)
111 search_even(0);
112 else
113 {
114 int x0, y0, x1, y1;
115
116 x0 = n / 2, y1 = n / 2;
117 for (x1 = 0; x1 < n / 2 - 1; x1++)
118 for (y0 = x1 + 1; y0 < n / 2; y0++)
119 if (abs(x0 - x1) != abs(y0 - y1))
120 {
121 x[y0] = x[y1] = true;
122 LR[x0 - y0] = RL[x0 + y0] = true;
123 LR[x1 - y1] = RL[x1 + y1] = true;
124
125 search_odd(0, x0, x1);
126
127 x[y0] = x[y1] = false;
128 LR[x0 - y0] = RL[x0 + y0] = false;
129 LR[x1 - y1] = RL[x1 + y1] = false;
130 }
131 x[n / 2] = LR[0] = RL[n - 1] = true;
132 search_odd(0, n / 2, n / 2);
133 x[n / 2] = LR[0] = RL[n - 1] = false;
134 }
135
136 cout << cnt << endl;
137
138 return 0;
139 }
140