本文主要是介绍POJ3414 Pots（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给两个不同容量的杯子，要求经过最少的操作使其中一个杯子中有cL水
要点：
也就是BFS题，只不过这题每个节点有6种方向
| 15304559 | Seasonal | 3414 | Accepted | 212K | 0MS | C++ | 2024B | 2016-03-23 19:34:10 |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define min(a,b) a>b?b:a
int a, b, c;
char str[6][100] = { "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)" };
int vis[105][105];//用数组记录是否到过，这样就不会走回头路了，保证输出最短路径
int step;struct node
{int a, b, num, pre;//num用来存储进行的操作
}que[105*105];void print(int i)//递归倒序输出
{if (que[i].pre != -1)//因为达到c后不需要操作，所以没有尾巴需要输出，同理头部也不需要{print(que[i].pre);printf("%s\n", str[que[i].num]);}
}
void bfs()
{int front = 0, rear = 1;que[0].a = que[0].b = 0;que[0].pre = -1;vis[0][0] = 1;while (front < rear){int count = rear - front;while (count--)//因为要统计操作次数，所以加一个while，其实如果不算操作数不加效果一样的{node now = que[front];if (now.a == c || now.b == c){printf("%d\n", step);print(front);return;}if (!vis[a][now.b]){que[rear].num = 0;que[rear].pre = front;que[rear].a = a;que[rear].b = now.b;vis[a][now.b] = 1;rear++;}if (!vis[now.a][b]){que[rear].num = 1;que[rear].pre = front;que[rear].a = now.a;que[rear].b = b;vis[now.a][b] = 1;rear++;}if (!vis[0][now.b]){que[rear].num = 2;que[rear].pre = front;que[rear].a = 0;que[rear].b = now.b;vis[0][now.b] = 1;rear++;}if (!vis[now.a][0]){que[rear].num = 3;que[rear].pre = front;que[rear].a = now.a;que[rear].b = 0;vis[now.a][0] = 1;rear++;}int wat1 = min(now.a, b - now.b);//防止溢出，所以两个取小if (!vis[now.a - wat1][now.b + wat1]){que[rear].num = 4;que[rear].pre = front;que[rear].a = now.a-wat1;que[rear].b = now.b+wat1;vis[now.a - wat1][now.b + wat1]=1;rear++;}int wat2 = min(a - now.a, now.b);if (!vis[now.a + wat2][now.b - wat2]){que[rear].num = 5;que[rear].pre = front;que[rear].a = now.a + wat2;que[rear].b = now.b - wat2;vis[now.a + wat2][now.b - wat2]=1;rear++;}front++;//出队}step++;}printf("impossible\n");
}int main()
{while (~scanf("%d%d%d", &a, &b, &c)){step = 0;memset(vis, 0, sizeof(vis));bfs();}return 0;
}这篇关于POJ3414 Pots（BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
