| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 15502 | Accepted: 6529 | Special Judge | ||
Description
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)
题意
有两个杯子，分别给出容量，然后我们对它做的有三种操作：
- 充满1或2杯子
- 倒掉1或2杯子
- 从1倒进2或从2倒进1
问，怎么样在最少的操作次数下让某一个杯子刚好达到指定量。
思路
我们可以认为初始状态两个杯子都是空的，然后对于每一种操作都算是一种状态，把它加入队列，然后对队列中的所有状态再进行下一次操作，也就是bfs啦！
不过需要注意的是，我们不能让同一个状态被加入队列两次（防止爆栈），因此要过滤一些，已知a,b小于100，因此可以用一个二维数组来存储某种状态是否被访问过。
最终输出最短的操作次数与步骤。
也不知道我是为了图想起来简单还是什么，所有的操作都是一个单独的判断，看起来代码略长。。。
AC 代码
#include <iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
typedef __int64 LL;
bool visited[105][105];
struct node
{
int left;
int right;
int time;
string path;
void init(int left,int right,string path,int time)
{
this->left=left;
this->right=right;
this->path=path;
this->time=time;
}
};
void bfs(int left,int right,int c)
{
queue<node>sk;
bool flag=false;
node s;
s.init(0,0,"",0);
visited[0][0]=true;
sk.push(s);
while(!sk.empty())
{
node p=sk.front();
sk.pop();
if(p.left==c||p.right==c)
{
cout<<p.time<<endl<<p.path;
flag=true;
return;
}
node tmp;
if(!visited[left][p.right]) //充满1
{
tmp.init(left,p.right,p.path+"FILL(1)\n",p.time+1);
visited[left][p.right]=true;
sk.push(tmp);
}
if(!visited[p.left][right]) //充满2
{
tmp.init(p.left,right,p.path+"FILL(2)\n",p.time+1);
visited[p.left][right]=true;
sk.push(tmp);
}
if(!visited[0][p.right]) //释放1
{
tmp.init(0,p.right,p.path+"DROP(1)\n",p.time+1);
visited[0][p.right]=true;
sk.push(tmp);
}
if(!visited[p.left][0]) //释放2
{
tmp.init(p.left,0,p.path+"DROP(2)\n",p.time+1);
visited[p.left][0]=true;
sk.push(tmp);
}
if(left-p.left<p.right&&!visited[left][p.right-(left-p.left)]) //从2到1
{
tmp.init(left,p.right-(left-p.left),p.path+"POUR(2,1)\n",p.time+1);
visited[left][p.right-(left-p.left)]=true;
sk.push(tmp);
}
else if(left-p.left>=p.right&&!visited[p.left+p.right][0])
{
tmp.init(p.left+p.right,0,p.path+"POUR(2,1)\n",p.time+1);
visited[p.left+p.right][0]=true;
sk.push(tmp);
}
if(p.left<=right-p.right&&!visited[0][p.left+p.right]) //从1到2
{
tmp.init(0,p.left+p.right,p.path+"POUR(1,2)\n",p.time+1);
visited[0][p.left+p.right]=true;
sk.push(tmp);
}
else if(p.left>right-p.right&&!visited[p.left-(right-p.right)][right])
{
tmp.init(p.left-(right-p.right),right,p.path+"POUR(1,2)\n",p.time+1);
visited[p.left-(right-p.right)][right]=true;
sk.push(tmp);
}
}
if(!flag)
printf("impossible\n");
}
int main()
{
int a,b,c;
while(~scanf("%d%d%d",&a,&b,&c))
{
memset(visited,false,sizeof(visited));
bfs(a,b,c);
}
}
