http://acm.pku.edu.cn/JudgeOnline/problem?id=3414又是一道廣搜題，可這次卻有個(gè)不一樣的地方，除了求出最短步數(shù)外，還要輸出最短路徑出來(lái)。在原來(lái)結(jié)點(diǎn)的基礎(chǔ)上，增加pre和flag兩個(gè)變量，分別記錄父結(jié)點(diǎn)在隊(duì)列中的位置和進(jìn)行哪種操作。記錄最短路徑讓我費(fèi)了一些周折。看來(lái)這里還是不很熟悉，以后得多加練習(xí)和思考c
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 int a,b,c;
5 typedef struct node{
6 int liter1,liter2,step,pre,flag;
7 }Node;
8 typedef struct queue{
9 Node q[11000];
10 int front,rear;
11 }Queue;
12 Queue Q;
13 int path[11000],j;
14 int visit[101][101];
15 void bfs();
16 int main()
17 {
18 while(scanf("%d%d%d",&a,&b,&c) != EOF)
19 bfs();
20 system("pause");
21 return 0;
22 }
23
24 void bfs()
25 {
26 Node pot;
27 Node lx,lc;
28 memset(visit,0,sizeof(visit));
29 pot.liter1 = 0;
30 pot.liter2 = 0;
31 pot.step = 0;
32 pot.pre = -1;
33 Q.front = Q.rear = 1;
34 Q.q[Q.rear++] = pot;
35 visit[0][0] = 1;
36 while(Q.front != Q.rear){
37 lc = Q.q[Q.front++];
38 if(lc.liter1 == c || lc.liter2 == c)break;
39 for(int i = 1;i < 7;i++){
40 if(i == 1){
41 lx.liter1 = a;
42 lx.liter2 = lc.liter2;
43 lx.step = lc.step + 1;
44 lx.pre = Q.front-1;
45 lx.flag = i;
46 if(visit[lx.liter1][lx.liter2] == 0){
47 visit[lx.liter1][lx.liter2] = 1;
48 Q.q[Q.rear++] = lx;
49 }
50 }
51 if(i == 2){
52 lx.liter1 = lc.liter1;
53 lx.liter2 = b;
54 lx.step = lc.step + 1;
55 lx.pre = Q.front-1;
56 lx.flag = i;
57 if(visit[lx.liter1][lx.liter2] == 0){
58 visit[lx.liter1][lx.liter2] = 1;
59 Q.q[Q.rear++] = lx;
60 }
61 }
62 if(i == 3){
63 lx.liter1 = 0;
64 lx.liter2 = lc.liter2;
65 lx.step = lc.step + 1;
66 lx.pre = Q.front-1;
67 lx.flag = i;
68 if(visit[lx.liter1][lx.liter2] == 0){
69 visit[lx.liter1][lx.liter2] = 1;
70 Q.q[Q.rear++] = lx;
71 }
72 }
73 if(i == 4){
74 lx.liter1 = lc.liter1;
75 lx.liter2 = 0;
76 lx.step = lc.step + 1;
77 lx.pre = Q.front-1;
78 lx.flag = i;
79 if(visit[lx.liter1][lx.liter2] == 0){
80 visit[lx.liter1][lx.liter2] = 1;
81 Q.q[Q.rear++] = lx;
82 }
83 }
84 if(i == 5){//2 to 1
85 if(lc.liter1 + lc.liter2 > a){
86 lx.liter1 = a;
87 lx.liter2 = lc.liter1 + lc.liter2 - a;
88 }
89 else{
90 lx.liter1 = lc.liter1 + lc.liter2;
91 lx.liter2 = 0;
92 }
93 lx.step = lc.step + 1;
94 lx.pre = Q.front-1;
95 lx.flag = i;
96
97 if(visit[lx.liter1][lx.liter2] == 0){
98 visit[lx.liter1][lx.liter2] = 1;
99 Q.q[Q.rear++] = lx;
100 }
101 }
102 if(i == 6){//1 to 2
103 if(lc.liter1 + lc.liter2 > b){
104 lx.liter1 = lc.liter1 + lc.liter2 - b;
105 lx.liter2 = b;
106 }
107 else{
108 lx.liter1 = 0;
109 lx.liter2 = lc.liter1 + lc.liter2;
110 }
111 lx.step = lc.step + 1;
112 lx.pre = Q.front-1;
113 lx.flag = i;
114
115 if(visit[lx.liter1][lx.liter2] == 0){
116 visit[lx.liter1][lx.liter2] = 1;
117 Q.q[Q.rear++] = lx;
118 }
119 }
120 }
121 }
122 if(Q.front == Q.rear){
123 printf("impossible\n");
124 return;
125 }
126 j = 0;
127 for(int i = Q.front-1;i>=0;){
128 path[j++] = i;
129 i = Q.q[i].pre;
130 }
131 printf("%d\n",Q.q[Q.front-1].step);
132 for(int i = j-1;i>= 0;i--){
133 switch(Q.q[path[i]].flag){
134 case 1:printf("FILL(1)\n");break;
135 case 2:printf("FILL(2)\n");break;
136 case 3:printf("DROP(1)\n");break;
137 case 4:printf("DROP(2)\n");break;
138 case 5:printf("POUR(2,1)\n");break;
139 case 6:printf("POUR(1,2)\n");break;
140 }
141 }
142
143 }
code