问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1166思路:
首先，观察题意，可以看出对于每一种Move，最多只需执行4次
一共存在9种不同的Move，因此可以尝试枚举出所有的可能，这样的复杂度是: 4^9
1 #define CLK_NUM 9
2 #define MV_NUM 9
3 #define DIAL_NUM 4
4 int clocks[CLK_NUM];
5 int moves[MV_NUM][CLK_NUM] = {
6 {1, 1, 0, 1, 1, 0, 0, 0, 0}, /* move: 1 */
7 {1, 1, 1, 0, 0, 0, 0, 0, 0}, /* move: 2 */
8 {0, 1, 1, 0, 1, 1, 0, 0, 0}, /* move: 3 */
9 {1, 0, 0, 1, 0, 0, 1, 0, 0}, /* move: 4 */
10 {0, 1, 0, 1, 1, 1, 0, 1, 0}, /* move: 5 */
11 {0, 0, 1, 0, 0, 1, 0, 0, 1}, /* move: 6 */
12 {0, 0, 0, 1, 1, 0, 1, 1, 0}, /* move: 7 */
13 {0, 0, 0, 0, 0, 0, 1, 1, 1}, /* move: 8 */
14 {0, 0, 0, 0, 1, 1, 0, 1, 1} /* move: 9 */
15 };
16 int mv_cur[MV_NUM*4]; /* 4 times a circle for each move */
17 int mv_cur_num;
18 int flag;
19
20 int
21 is_ok()
22 {
23 int i;
24 for(i=0; i<CLK_NUM; i++)
25 if(clocks[i] % DIAL_NUM != 0)
26 return 0;
27 return 1;
28 }
29
30 void
31 dfs(int depth)
32 {
33 if(depth > MV_NUM || flag)
34 return;
35 int i, j, k;
36 if(is_ok()) {
37 flag = 1;
38 for(i=0; i<mv_cur_num; i++)
39 printf("%d ", mv_cur[i]+1);
40 printf("\n");
41 return;
42 }
43 for(j=0; j<4; j++) { /* each move test 4 times */
44 for(k=0; k<j; k++) {
45 for(i=0; i<CLK_NUM; i++)
46 clocks[i] += moves[depth][i];
47 mv_cur[mv_cur_num] = depth;
48 mv_cur_num += 1;
49 }
50 dfs(depth+1);
51 for(k=0; k<j; k++) {
52 for(i=0; i<CLK_NUM; i++)
53 clocks[i] -= moves[depth][i];
54 mv_cur_num -= 1;
55 }
56 }
57 }