問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1606http://acm.pku.edu.cn/JudgeOnline/problem?id=3414思路:
典型的BFS
好玩的就是如何來處理輸出，每個狀態包含一個指向前一個狀態的指針
代碼:
1 #define QUEUE_LEN 10000
2 #define MAX_VOL 101
3 const char ops[][12] = {
4 "FILL(1)",
5 "FILL(2)",
6 "DROP(1)",
7 "DROP(2)",
8 "POUR(1,2)",
9 "POUR(2,1)" };
10 int vola, volb, target;
11 int head, tail;
12 int visited[MAX_VOL][MAX_VOL];
13 struct EACH {
14 int a, b;
15 int opnum;
16 int opidx;
17 struct EACH *pre;
18 } queue[QUEUE_LEN];
19
20 #define ADD(na, nb, num, idx) ++tail; \
21 queue[tail].a = na; \
22 queue[tail].b = nb; \
23 queue[tail].opnum = num+1; \
24 queue[tail].opidx = idx; \
25 queue[tail].pre = queue+head; \
26 visited[na][nb] = 1;
27
28 void
29 output(struct EACH *item)
30 {
31 if(item == NULL)
32 return;
33 output(item->pre);
34 if(item->opidx >= 0)
35 printf("%s\n", ops[item->opidx]);
36 }
37
38 void
39 bfs()
40 {
41 int cur_a, cur_b, ta, tb, cur_opnum;
42 queue[tail].a = 0;
43 queue[tail].b = 0;
44 queue[tail].opnum = 0;
45 queue[tail].opidx = -1;
46 queue[tail].pre = NULL;
47 visited[0][0] = 1;
48 while(head < tail) {
49 ++head;
50 cur_a = queue[head].a;
51 cur_b = queue[head].b;
52 cur_opnum = queue[head].opnum;
53 if(cur_a==target || cur_b==target) {
54 printf("%d\n", cur_opnum);
55 output(queue+head);
56 return;
57 }
58 if(!visited[vola][cur_b]) { /* FILL(1) */
59 ADD(vola, cur_b, cur_opnum, 0);
60 }
61 if(!visited[cur_a][volb]) { /* FILL(2) */
62 ADD(cur_a, volb, cur_opnum, 1);
63 }
64 if(!visited[0][cur_b]) { /* DROP(1) */
65 ADD(0, cur_b, cur_opnum, 2);
66 }
67 if(!visited[cur_a][0]) { /* DROP(2) */
68 ADD(cur_a, 0, cur_opnum, 3);
69 }
70 /* POUR(1,2) */
71 if(cur_a+cur_b > volb) {
72 ta = cur_a+cur_b-volb;
73 tb = volb;
74 if(!visited[ta][tb]) {
75 ADD(ta, tb, cur_opnum, 4);
76 }
77 } else {
78 ta = 0;
79 tb = cur_a + cur_b;
80 if(!visited[ta][tb]) {
81 ADD(ta, tb, cur_opnum, 4);
82 }
83 }
84 /* POUR(2,1) */
85 if(cur_a+cur_b > vola) {
86 ta = vola;
87 tb = cur_a+cur_b-vola;
88 if(!visited[ta][tb]) {
89 ADD(ta, tb, cur_opnum, 5);
90 }
91 } else {
92 ta = cur_a + cur_b;
93 tb = 0;
94 if(!visited[ta][tb]) {
95 ADD(ta, tb, cur_opnum, 5);
96 }
97 }
98 }
99 printf("impossible\n");
100 }