USACO Section 1.5: Checker Challenge
8451 ワード
この問題の鍵は半分の枝を切ることだ.
1 /*
2 ID: leetcod3
3 PROG: checker
4 LANG: C++
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <map>
10 #include <vector>
11 #include <set>
12 #include <algorithm>
13 #include <queue>
14 #include <cmath>
15 #include <list>
16 #include <cstring>
17 #include <cstdlib>
18 #include <limits>
19 #include <stack>
20
21 using namespace std;
22
23 ofstream fout ("checker.out");
24 ifstream fin ("checker.in");
25
26 int N;
27 bool col[14];
28 int rec[14];
29 int total = 0;
30 int print_total = 0;
31
32 bool intersect(int dep, int x) {
33 for (int i = 0; i < dep; ++i) {
34 if (dep - i == abs(rec[i]-x)) return true;
35 }
36 return false;
37 }
38
39 void dfs(int dep, int n) {
40 if (dep == N) {
41 total++;
42 if (print_total++ < 3) {
43 for (int i = 0; i < N-1; ++i) fout << rec[i]+1 << " ";
44 fout << rec[N-1]+1 << endl;
45 }
46 if (N > 6 && rec[0] < N/2) total++;
47 return;
48 }
49 for (int i = 0; i < n; i++) {
50 if (!col[i] && !intersect(dep, i)) {
51 col[i] = true;
52 rec[dep] = i;
53 dfs(dep+1, N);
54 col[i] = false;
55 }
56 }
57 }
58
59 int main()
60 {
61 fin >> N;
62 memset(col, false, sizeof(col));
63 memset(rec, 0, sizeof(rec));
64 dfs(0, N > 6? (N+1)/2 : N);
65 fout << total << endl;
66 return 0;
67 }