本文共 1785 字，大约阅读时间需要 5 分钟。
题意：两个壶倒水，三种操作，两个桶其中一个满足等于C的最少操作，输出路径。注意a,b互倒的时候能不能倒满，或者还有剩下的。
a->b || b->a || a->0 || b->0 || a->A || b->B (0<=a<=A&&0<=b<=B)
思路：虽说是BFS但是情况就这几种，分别写出来之后判断即可。输出路径可以用递归，我这里用了string来存。
#include #include #include #include #include #include #include using namespace std;const int maxn = 1000+5;char *S[3] ={ "FILL","POUR","DROP"};int A,B,C;int vis[maxn][maxn];struct node{ int a,b; string opt[maxn]; //存路径再输出 int step ;}ans;bool check(node x){ if(x.a == C||x.b == C) return true; return false;}int bfs(){ queue Q; node p,t; p.a = p.b = p.step = 0; Q.push(p); while(Q.size()){ p = Q.front(); Q.pop(); if(check(p)) { ans = p; return true; } //DROP(1) if(!vis[0][p.b]){ t = p; t.a = 0; t.step++; t.opt[t.step] = "DROP(1)"; Q.push(t); vis[0][p.b] = 1; } //DROP(2) if(!vis[p.a][0]){ t = p; t.b = 0; t.step++; t.opt[t.step] = "DROP(2)"; Q.push(t); vis[p.a][0] = 1; } //FILL(1) if(!vis[A][p.b]){ t = p; t.a = A; t.step++; t.opt[t.step] = "FILL(1)"; Q.push(t); vis[A][p.b] = 1; } //FILL(2) if(!vis[p.a][B]){ t = p; t.b = B; t.step++; t.opt[t.step] = "FILL(2)"; Q.push(t); vis[p.a][B] = 1; } //POUR(2,1) if(!vis[p.b>(A-p.a)?A:(p.a+p.b)][p.b>(A-p.a)?(p.b-A+p.a):0]){ t = p; t.a = p.b>(A-p.a)?A:(p.a+p.b); t.b = p.b>(A-p.a)?(p.b-A+p.a):0; t.step++; t.opt[t.step] = "POUR(2,1)"; Q.push(t); vis[t.a][t.b] = 1; } //POUR(1,2) if(!vis[p.a>(B-p.b)?(p.a-B+p.b):0][p.a>(B-p.b)?B:(p.a+p.b)]){ t = p; t.a = p.a>(B-p.b)?(p.a-B+p.b):0; t.b = p.a>(B-p.b)?B:(p.a+p.b); t.step++; t.opt[t.step] = "POUR(1,2)"; Q.push(t); vis[t.a][t.b] = 1; } } return -1;}int main(){ while(~scanf("%d%d%d",&A,&B,&C)){ memset(vis,0,sizeof(vis)); if(bfs()>0){ cout< <
转载于:https://www.cnblogs.com/MIKORU/p/5796741.html