Posted on 2008-06-16 15:30
superman 阅读(1316)
评论(0) 编辑 收藏 引用 所属分类:
POJ
1 /* Accepted 340K 204MS G++ 1571B */
2 #include <iostream>
3
4 using namespace std;
5
6 enum { A, B, C, D, E, F, G, H, I };
7
8 int clocks[9];
9 int control[9][6] = {
10 {4, A, B, D, E},
11 {3, A, B, C},
12 {4, B, C, E, F},
13 {3, A, D, G},
14 {5, B, D, E, F, H},
15 {3, C, F, I},
16 {4, D, E, G, H},
17 {3, G, H, I},
18 {4, E, F, H, I}
19 };
20
21 int x[9];
22 int bestx[9], best = INT_MAX;
23 void search(int k)
24 {
25 if(k == 9)
26 {
27 for(int i = 0; i < 9; i++)
28 if(clocks[i])
29 return;
30
31 int cnt = 0;
32 for(int i = 0; i < 9; i++)
33 cnt += x[i];
34
35 if(cnt < best)
36 {
37 best = cnt;
38 for(int i = 0; i < 9; i++)
39 bestx[i] = x[i];
40 }
41 return;
42 }
43
44 x[k] = 0;
45 search(k + 1);
46
47 for(int i = 1; i <= 3; i++)
48 {
49 for(int j = 1; j <= control[k][0]; j++)
50 {
51 clocks[control[k][j]]++;
52 clocks[control[k][j]] %= 4;
53 }
54
55 x[k] = i;
56
57 search(k + 1);
58 }
59
60 for(int i = 1; i <= 3; i++)
61 for(int j = 1; j <= control[k][0]; j++)
62 if(clocks[control[k][j]] == 0)
63 clocks[control[k][j]] = 3;
64 else
65 clocks[control[k][j]]--;
66 }
67
68 int main()
69 {
70 for(int i = 0; i < 9; i++)
71 cin >> clocks[i];
72
73 search(0);
74
75 for(int i = 0; i < 9; i++)
76 for(int j = 0; j < bestx[i]; j++)
77 cout << i + 1 << ' ';
78 cout << endl;
79
80 return 0;
81 }
82