2152：花盆

来源：花匠小妙招时间：2024-11-24 05:48 更新：2024-11-28 08:37

最新推荐文章于 2024-11-21 11:23:25 发布

桃夭~ 于 2022-10-12 23:02:48 发布

总时间限制：

1000毫秒

内存限制：

65536kB

描述

给你两个罐子，体积分别为A升和B升。可以执行以下操作：

FILL(i ) 从水龙头中填充罐i (1 ≤ i ≤ 2)； DROP(i) 将罐i排空到排水管； POUR(i,j) 从锅i倒入锅j；在此操作之后，锅j已满（锅i中可能还剩一些水），或者锅i空了（其所有内容物都已移至锅j）。

编写一个程序，找出这些操作的最短可能序列，从而在其中一个罐子中产生恰好C升的水。

输入

第一行也是唯一一行是数字A、B和C。这些都是 1 到 100 范围内的整数，且C ≤max( A , B )。

输出

输出的第一行必须包含操作序列K的长度。以下K行必须分别描述一项操作。如果有多个最小长度的序列，则输出其中任何一个。如果无法达到预期的结果，文件的第一行也是唯一的行必须包含单词“不可能”。

样例输入

3 5 4

样例输出

填充（2）

倒(2,1)

掉落(1)

倒(2,1)

填充（2）

倒(2,1)

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct ping
{
int nowav,nowbv;
string work;
int father;
int leng;
}myqueue[1000000];
int visited[105][105];
string ans[100000];
int main()
{
memset(visited,0,sizeof(visited));
int A,B,C,flag=1;
cin>>A>>B>>C;
int qhead=0,qtail=1;
myqueue[qhead].nowav=0,myqueue[qhead].nowbv=0,myqueue[qhead].leng=0;
visited[0][0]=1;
while(qhead!=qtail)
{
ping s=myqueue[qhead];
if(s.nowav==C||s.nowbv==C){
flag=0;
break;}
if(s.nowav!=A&&!visited[A][s.nowbv])
{
myqueue[qtail].nowbv=s.nowbv;
myqueue[qtail].leng=s.leng+1;
myqueue[qtail].nowav=A;
myqueue[qtail].father=qhead;
myqueue[qtail].work="FILL(1)";
visited[A][s.nowbv]=1;
qtail++;
}
if(s.nowbv!=B&&!visited[s.nowav][B])
{
myqueue[qtail].nowav=s.nowav;
myqueue[qtail].leng=s.leng+1;
myqueue[qtail].nowbv=B;
myqueue[qtail].father=qhead;
myqueue[qtail].work="FILL(2)";
visited[s.nowav][B]=1;
qtail++;
}
if(s.nowav!=0&&!visited[0][s.nowbv])
{
myqueue[qtail].nowbv=s.nowbv;
myqueue[qtail].leng=s.leng+1;
myqueue[qtail].nowav=0;
myqueue[qtail].father=qhead;
myqueue[qtail].work="DROP(1)";
visited[0][s.nowbv]=1;
qtail++;
}
if(s.nowbv!=0&&!visited[s.nowav][0])
{
myqueue[qtail].nowav=s.nowav;
myqueue[qtail].leng=s.leng+1;
myqueue[qtail].nowbv=0;
myqueue[qtail].father=qhead;
myqueue[qtail].work="DROP(2)";
visited[s.nowav][0]=1;
qtail++;
}
if(s.nowbv+s.nowav<B&&!visited[0][s.nowbv+s.nowav])
{
myqueue[qtail].leng=s.leng+1;
myqueue[qtail].nowbv=s.nowbv+s.nowav;
myqueue[qtail].nowav=0;
myqueue[qtail].father=qhead;
myqueue[qtail].work="POUR(1,2)";
visited[0][s.nowbv+s.nowav]=1;
qtail++;
}
if(s.nowbv+s.nowav>=B&&!visited[s.nowbv+s.nowav-B][B])
{
myqueue[qtail].leng=s.leng+1;
myqueue[qtail].nowbv=B;
myqueue[qtail].nowav=s.nowbv+s.nowav-B;
myqueue[qtail].father=qhead;
myqueue[qtail].work="POUR(1,2)";
visited[s.nowbv+s.nowav-B][B]=1;
qtail++;
}
if(s.nowbv+s.nowav<A&&!visited[s.nowbv+s.nowav][0])
{
myqueue[qtail].leng=s.leng+1;
myqueue[qtail].nowav=s.nowbv+s.nowav;
myqueue[qtail].nowbv=0;
myqueue[qtail].father=qhead;
myqueue[qtail].work="POUR(2,1)";
visited[s.nowbv+s.nowav][0]=1;
qtail++;
}
if(s.nowbv+s.nowav>=A&&!visited[A][s.nowbv+s.nowav-A])
{
myqueue[qtail].leng=s.leng+1;
myqueue[qtail].nowav=A;
myqueue[qtail].nowbv=s.nowbv+s.nowav-A;
myqueue[qtail].father=qhead;
myqueue[qtail].work="POUR(2,1)";
visited[A][s.nowbv+s.nowav-A]=1;
qtail++;
}
qhead++;
}
if(flag)
{
cout<<"impossible";
return 0;
}
int K=myqueue[qhead].leng;
cout<<K<<endl;
for(int i=1;i<=K;++i)
{
ans[i]=myqueue[qhead].work;
qhead=myqueue[qhead].father;
}
for(int i=K;i>=1;--i)
{
cout<<ans[i];
if(i!=1)
cout<<endl;
}
}