poj 3414BFS
题意：给出两个容积分别为 a 和 b 的pot，按照以下三种操作方式，求出能否在一定步数后，使者两个pot的其中一个的水量为c。1.FILL(i)：将ipot倒满水。
2.DROP(i)：将ipot倒空水。
3.POUR(i,j)： 将ipot的水倒到jpot上，直至要么ipot为空，要么jpot为满。
思路：bfs求最短路径，与1426类似，只是每个节点的子节点数为6个而已。
代码如下：
#include<iostream>using namespace std;const int Max = 101; struct node{ int ope;int a;int b;node *pre;}que;//队列结点，ope记录第几种操作，a,b记录此结点两个pot的水的数量。bool vis;char str = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"}; // 各操作对应输出的字符串。 int min(int a, int b){ return a < b ? a : b;} void print(node now){ if(now.pre != NULL){ print(*now.pre); cout << str << endl; }}//递归输出答案个人认为写得很巧妙 void bfs(int a, int b, int c){ int steps = 0; int head = 0, tail = 1; que.a = que.b = 0; que.pre = NULL; while(tail - head > 0){ int count = tail - head; while(count --)//每一种情况都要考虑六种情况{ node now = que; if(now.a == c || now.b == c){ cout << steps << endl; print(now); return; } if(!vis){ que.ope = 0; que.a = a; que.b = now.b; que.pre = &que; vis = true; tail ++; } if(!vis){ que.ope = 1; que.a = now.a; que.b = b; que.pre = &que; vis = true; tail ++; } if(!vis){ que.ope = 2; que.a = 0; que.b = now.b; que.pre = &que; vis = true; tail ++; } if(!vis) { que.ope = 3; que.a = now.a; que.b = 0; que.pre = &que; vis = true; tail ++; } int wat1 = min(now.a, b - now.b); if(!vis){ que.ope = 4; que.a = now.a - wat1; que.b = now.b + wat1; que.pre = &que; vis = true; tail ++; } int wat2 = min(a - now.a, now.b); if(!vis){ que.ope = 5; que.a = now.a + wat2; que.b = now.b - wat2; que.pre = &que; vis = true; tail ++; } head ++; } steps ++; } cout << "impossible" << endl;} int main(){ int a, b, c; cin >> a >> b >> c; memset(vis, false, sizeof(vis));//初始化 vis = true;//初始化 bfs(a, b, c); return 0;}
页:
[1]