POJ 3414 H-Pots

题目如下：

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;

DROP(i) empty the pot i to the drain;

POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

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. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. 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

FILL(2)

POUR(2,1)

DROP(1)

POUR(2,1)

FILL(2)

POUR(2,1)

解题思路：

这道题首先是bfs的一道模拟题，我们可以将6种操作看成是遍历的6个方向。这道题还需要输出操作的过程，因此这道题我们需要记忆化搜索，所以我们需要用数组来模拟队列，将遍历的每个状态都记录上该状态之前的状态。（详细可以去了解一下Kuang bin 的 迷宫问题，用数组模拟队列的原因就是可以在数组中记录下已经访问过的点。当搜索到最终结果时，我们就可以通过数组中已经访问过的点来进行递归输出) 搜索到结果之后，将结果进行返回。根据最终的结果来进行递归（每次递归都要去寻找该状态的之前状态)，从而得到开始状态-最终状态的操作过程。并且我们还要记录一下已经访问过的点，这个时候我们可以根据A,B容器中水的不同情况来表示该点。（例如：A的容器为0，B的容器为5,这种情况的点就是(0,5)，我们需要将这个点设置为已经访问过，从而避免重复添加到队列中。当这个点没有访问过的话，我们就需要将其添加到队列) 注意：这道题并不是多组输入输出！所以输出完情况后直接退出程序就行。

迷宫问题的笔记如下： https://www.cnblogs.com/gao79135/p/14085114.html

将搜索到的状态添加到队列后，我们需要进行判断，若搜索的状态满足条件则退出，并进行递归输出结果。不满足的话输出impossible。并且这道题中容器的容量最多到达100，那也就是说一个容器就有100种情况，两个容器共有10000种情况，因此数组的大小为10000。但是按照本题来讲，遍历的情况远远到不了10000，所以我们就不能遍历10000次来找到最终的结果。所以，我们可以设置一个指针front，每在队列中添加一个状态，我们就需要将front++。当搜索完之后，front之前的所有状态即为搜索到的状态。因此我们就在小于front的范围中进行搜索就好。（front之后的所有内容都是空的，如果遍历到了front之后的内容，结果就会WA！！！！)

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
bool status[102][102];   //定义A,B容器中水的所有状态(由于水的容量最多到100,所以status数组光开到100是不够的！)
int A, B, C;             //定义A容器容量、B容器容量、满足的容量数
int K = 0;               //定义最小操作数K
int flag = 0;
string direction[6] = { "FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)" };  //定义六种操作
struct Point
{
	int Awater;          //定义A罐子的水量
	int Bwater;          //定义B罐子的水量
	int pre;             //定义该状态的上一步在队列中的下标
	int operation;       //定义执行了什么操作
} Q[10000];              //定义以数组实现的队列
void dfs(struct Point point);     //定义进行递归的函数
struct Point bfs();      //定义进行bfs的函数


struct Point bfs()
{
	int i;
	int atemp, btemp;        //定义操作完的A,B容器容量
	int now;                 //定义当前状态在数组中的下标
	Q[0].Awater = 0;         //定义刚开始状态A容器容量为0
	Q[0].Bwater = 0;         //定义刚开始状态B容器容量为0
	Q[0].pre = -1;           //定义刚开始状态的上一步下标为-1
	status[0][0] = true;     
	int front=1,j=0; //定义队列的对首和队尾指针
	while (true)
	{
		now = j;            //将当前状态在数组的下标设置为now
		if (now >= front)   //如果当前的now超过了数组当中的指针front(代表now一直遍历的都是搜索到的状态)
		{
			break;
		}
		for (i = 0; i < 6; i++)
		{
			atemp = Q[now].Awater;
			btemp = Q[now].Bwater;
			if (i == 0)
			{
				if (atemp == A)
				{
					continue;
				}
				atemp = A;  //将A容器进行倒满，B容器不做修改
			}
			else if (i == 1)
			{
				if (btemp == B)
				{
					continue;
				}
				btemp = B;  //将B容器进行倒满，A容器不做修改
			}
			else if (i == 2)
			{
				if (atemp == 0)
				{
					continue;
				}
				atemp = 0;  //将A容器进行抽干，B容器不做修改
			}
			else if (i == 3)
			{
				if (btemp == 0)
				{
					continue;
				}
				btemp = 0;  //将B容器进行抽干，A容器不做修改
			}
			else if (i == 4)
			{
				int pour = min(atemp, B - btemp);      //让A容器中水的容量和B容器中剩余的容量取最小值
				atemp -= pour;                      //从A容器中取出水
				btemp += pour;                      //让B容器接收A取出的水
				if (pour == 0)                      //如果A容器中水为空，或者B容器中没有剩余的容量，那么从A容器中倒出水给B，则两容器中的水不会做任何改变
				{
					continue;                       //若不会做任何改变就直接进行下一次操作
				}
			}
			else if (i == 5)
			{
				int pour = min(btemp, A - atemp);      //跟上述情况相反，这里就不再阐述
				btemp -= pour;
				atemp += pour;
				if (pour == 0)
				{
					continue;
				}
			}
			if (status[atemp][btemp] == false)     //若本次A,B容器中水的状态没有搜索过，那么把它加入到数组中。若加入过则搜索其它状况
			{
				Q[front].Awater = atemp;           //A容器容量赋值
				Q[front].Bwater = btemp;           //B容器容量赋值
				Q[front].pre = now;                //记录移动后状态的上一个状态在数组中的下标(now)
				Q[front].operation = i;            //记录操作
				status[atemp][btemp] = true;
				front++;                           //将数组下标+1
			}
			if (Q[now].Awater == C || Q[now].Bwater == C)  //如果搜索的状态中A容器或B容器中的容量到了满足的容量数，那么就进行退出
			{
				return Q[now];
			}
		}
		j++;
	}
	struct Point bad;
	bad.pre = -10000;
	return bad;                                   //如果没有符合的容量数，直接退出
}

void dfs(struct Point point)
{
	if (point.pre != -1)
	{
		K++;
	}
	if (point.pre == -10000)
	{
		cout << "impossible" << endl;
		return;
	}
	if (point.pre == -1)                             //如果递归到了初始状态（两容器水都为0时)
	{
		return;
	}
	dfs(Q[point.pre]);
	if (flag == 0)
	{
		cout << K << endl;
		flag = 1;
	}
	cout << direction[point.operation] << endl;
}

int main()
{
	struct Point end_point;    
	scanf("%d %d %d", &A, &B, &C);
	end_point = bfs();
	dfs(end_point);
}

POJ 3414 H-Pots

原文：https://www.cnblogs.com/gao79135/p/14088520.html