本文主要是介绍poj 3414 Pots 广度优先搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目意思：给出两个杯子容积，初始都为空杯子，给出目标水量，可以执行一些操作，分别是倒空一个杯子，倒满一个杯子，和将一个杯子的水倒到另一个中，问得到目标水量要进行至少多少次以及每次都是什么
FILL（1）表示倒满1杯子，POUR（2，1）表示将2杯子里的水倒进1杯子中，DROP（1）表示倒空1杯子。
本体为广度优先生成树，每次对六种操作进行广度搜索，用二维数组进行状态是否出现过的标记，并记录每次出现的节点的父节点，最后用递归进行输出。
Description
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:
Input
On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).
Output
The first line of the output must contain the length of the sequence of operations K. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.
Sample Input
3 5 4
Sample Output
6
Hint
#include<stdio.h>
#include<string.h>
int a,b,p;
struct node
{int a,b,step;
} q[1000],t,f;
int s[101][101];
int bfs()
{int i;int qian=1;int hou=0;q[0].a=0;q[0].b=0;q[0].step=0;s[0][0]=1;while(qian>hou){t=q[hou++];if(t.a==p||t.b==p){printf("%d\n",t.step);return 0;}f.a=a;f.b=t.b;if(s[f.a][f.b]==0){f.step=t.step+1;q[qian++]=f;s[f.a][f.b]=1;}f.a=t.a;f.b=b;if(s[f.a][f.b]==0){f.step=t.step+1;q[qian++]=f;s[f.a][f.b]=1;}f.a=0;f.b=t.b;if(s[f.a][f.b]==0){f.step=t.step+1;q[qian++]=f;s[f.a][f.b]=1;}f.a=t.a;f.b=0;if(s[f.a][f.b]==0){f.step=t.step+1;q[qian++]=f;s[f.a][f.b]=1;}f.b=t.b+t.a;f.a=t.a-(b-t.b);if(f.b>=b)f.b=b;if(f.a<0)f.a=0;if(s[f.a][f.b]==0){f.step=t.step+1;q[qian++]=f;s[f.a][f.b]=1;}f.a=t.a+t.b;f.b=t.b-(a-t.a);if(f.a>=a)f.a=a;if(f.b<0)f.b=0;if(s[f.a][f.b]==0){f.step=t.step+1;q[qian++]=f;s[f.a][f.b]=1;}}printf("impossible\n");return 0;
}
int main()
{while(scanf("%d %d %d",&a,&b,&p)!=EOF){memset(s,0,sizeof(s));bfs();}return 0;
}这篇关于poj 3414 Pots 广度优先搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
