POJ 3414 Pots——bfs搜索+dfs输出

POJ 3414 Pots——bfs搜索+dfs输出

题意：给定两个水杯的容量A B以及一个数C，两个水杯一开始为空，要求用最少的操作数把A或B内的水变为C，并打印路径。

每次操作可以把一个水杯灌满水，或者把一个水杯的水全部倒掉，或者把一个水杯的水尽量倒在另一个水杯内

思路：bfs搜索，每次向队列中加6个状态就可以了，关键是打印路径，比较容易想到的是把之前的路径放在每个状态中，但是这会浪费大量的时间和空间，正确做法是给每个状态编号，然后用link数组将相对应的状态链接在一起，然后dfs打印路径即可，具体参考代码

#include #include #include #include #include using namespace std;const int maxn = 110;int A, B, C, cnt, ans, vis[maxn][maxn], link[maxn * maxn];struct State { int a, b, step, id, flag;}state[maxn * maxn], temp;queue q;void update(int a, int b, int flag, int step, int root) { if (!vis[a][b]) { vis[a][b] = 1; state[cnt].a = a, state[cnt].b = b, state[cnt].flag = flag, state[cnt].id = cnt, state[cnt].step = step; link[cnt] = root; q.push(state[cnt++]); }}void output(int x) { if (x == 0) return; output(link[x]); switch (state[x].flag) { case 1: printf("FILL(1)\n"); break; case 2: printf("FILL(2)\n"); break; case 3: printf("DROP(1)\n"); break; case 4: printf("DROP(2)\n"); break; case 5: printf("POUR(1,2)\n"); break; case 6: printf("POUR(2,1)\n"); break; }}int main() { while (~scanf("%d %d %d", &A, &B, &C)) { cnt = 0; ans = -1; memset(vis, 0, sizeof(vis)); while (!q.empty()) q.pop(); state[cnt].a = state[cnt].b = state[cnt].flag = state[cnt].id = state[cnt].step = 0; vis[0][0] = 1; q.push(state[cnt++]); while (!q.empty()) { temp = q.front(); q.pop(); if (temp.a == C || temp.b == C) { ans = temp.id; break; } int a, b, root = temp.id; a = A, b = temp.b; update(a, b, 1, temp.step + 1, root); a = temp.a, b = B; update(a, b, 2, temp.step + 1, root); a = 0, b = temp.b; update(a, b, 3, temp.step + 1, root); a = temp.a, b = 0; update(a, b, 4, temp.step + 1, root); a = (temp.a+temp.b>B)?temp.a-B+temp.b:0, b = (temp.a+temp.b>B)?B:temp.a+temp.b; update(a, b, 5, temp.step + 1, root); a = (temp.a+temp.b>A)?A:temp.a+temp.b, b = (temp.a+temp.b>A)?temp.b-A+temp.a:0; update(a, b, 6, temp.step + 1, root); } if (ans == -1) printf("impossible\n"); else { printf("%d\n", state[ans].step); output(ans); int id = ans; } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。