本文共 2055 字，大约阅读时间需要 6 分钟。
题目链接：
思路：
因为有六种操作，所以六种操作中合法的都加入队列中BFS
如何去输出路径呢？
我们不妨设一个string数组，它的索引就和我们的步数有关，然后按顺序输出就可以了。
之后有一道题的记录路径的方式也比较巧妙：poj 3984 迷宫问题
具体代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std; 10 11 const int maxn = 1000+5; 12 char *S[3] ={ "FILL","POUR","DROP"}; 13 int A,B,C; 14 int vis[maxn][maxn]; 15 struct node{ 16 int a,b; 17 string opt[maxn]; //存路径再输出 18 int step ; 19 }ans; 20 bool check(node x){ 21 if(x.a == C||x.b == C) 22 return true; 23 return false; 24 } 25 int bfs(){ 26 queue Q; 27 node p,t; 28 p.a = p.b = p.step = 0; 29 Q.push(p); 30 while(Q.size()){ 31 p = Q.front(); 32 Q.pop(); 33 if(check(p)) { 34 ans = p; 35 return true; 36 } 37 //DROP(1) 38 if(!vis[0][p.b]){ 39 t = p; 40 t.a = 0; 41 t.step++; 42 t.opt[t.step] = "DROP(1)"; 43 Q.push(t); 44 vis[0][p.b] = 1; 45 } 46 //DROP(2) 47 if(!vis[p.a][0]){ 48 t = p; 49 t.b = 0; 50 t.step++; 51 t.opt[t.step] = "DROP(2)"; 52 Q.push(t); 53 vis[p.a][0] = 1; 54 } 55 //FILL(1) 56 if(!vis[A][p.b]){ 57 t = p; 58 t.a = A; 59 t.step++; 60 t.opt[t.step] = "FILL(1)"; 61 Q.push(t); 62 vis[A][p.b] = 1; 63 } 64 //FILL(2) 65 if(!vis[p.a][B]){ 66 t = p; 67 t.b = B; 68 t.step++; 69 t.opt[t.step] = "FILL(2)"; 70 Q.push(t); 71 vis[p.a][B] = 1; 72 } 73 //POUR(2,1) 74 if(!vis[p.b>(A-p.a)?A:(p.a+p.b)][p.b>(A-p.a)?(p.b-A+p.a):0]){ 75 t = p; 76 t.a = p.b>(A-p.a)?A:(p.a+p.b); 77 t.b = p.b>(A-p.a)?(p.b-A+p.a):0; 78 t.step++; 79 t.opt[t.step] = "POUR(2,1)"; 80 Q.push(t); 81 vis[t.a][t.b] = 1; 82 } 83 //POUR(1,2) 84 if(!vis[p.a>(B-p.b)?(p.a-B+p.b):0][p.a>(B-p.b)?B:(p.a+p.b)]){ 85 t = p; 86 t.a = p.a>(B-p.b)?(p.a-B+p.b):0; 87 t.b = p.a>(B-p.b)?B:(p.a+p.b); 88 t.step++; 89 t.opt[t.step] = "POUR(1,2)"; 90 Q.push(t); 91 vis[t.a][t.b] = 1; 92 } 93 } 94 return -1; 95 } 96 int main() 97 { 98 while(~scanf("%d%d%d",&A,&B,&C)){ 99 memset(vis,0,sizeof(vis));100 if(bfs()>0){101 cout< <
转载于:https://www.cnblogs.com/-Ackerman/p/11186592.html