$$\color{Purple}{kuangbin题解目录}$$
描述
给你两个罐子,容积分别为 $A$ 升和 $B$ 升。
现在,你可以进行如下三种操作:
FILL(i)
,将罐子 $i$($1 \\le i \\le 2$)灌满水。DROP(i)
,将罐子 $i$($1 \\le i \\le 2$)清空。POUR(i,j)
,将罐子 $i$ 中的水倒向罐子 $j$,直到罐子 $i$ 空了或罐子 $j$ 满了为止。
请问,至少多少次操作后,可以使得其中一个罐子里恰好有 $C$ 升水。
输入格式
共一行,三个整数 $A,B,C$。
输出格式
如果无解,则输出一行 impossible
即可。
否则,第一行输出一个整数,表示最少操作次数。
随后按顺序每行输出一个操作指令,格式参考题面。
数据范围
$1 \\le A,B,C \\le 100$,
$C \\le max(A,B)$。
输入样例:
3 5 4
输出样例:
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
思路
基于bfs的思想,将两个杯子分别看作坐标系中的$x$和$y$,去跑bfs即可,此时无非就6种情况,倒满$A$(来源于$B$或外界倒满),倒空$A$,倒满$B$(来源于$A$或外界倒满),倒空$B$.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 110
using namespace std;
int A,B,C;
struct node{
int x;
int y;
int step;
string op;
};
string res[6]={"FILL(1)", "FILL(2)", "DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int vis[MAXN][MAXN];
void bfs()
{
queue<node> q;
q.push({0,0,0,""});
vis[0][0]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
if(temp.x==C||temp.y==C)
{
//cout << temp.op << "***" << endl;
cout << temp.step << endl;
for(int i=0;i<temp.step;i++)
cout << res[temp.op[i]] << endl;
return ;
}
int temp1=min(temp.x,B-temp.y);
int temp2=min(temp.y,A-temp.x);
//倒满,倒空,A->B,B->A
int dir[6][2]={{A-temp.x,0},{0,B-temp.y},{-temp.x,0},{0,-temp.y},{-temp1,temp1},{temp2,-temp2}};
for(int i=0;i<=5;i++)
{
int dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(vis[dx][dy]==0)
{
char temp_op=i;
string s=temp.op+temp_op;
q.push({dx,dy,temp.step+1,s});
vis[dx][dy]=1;
}
}
}
printf("impossible\n");
}
int main()
{
scanf("%d %d %d",&A,&B,&C);
bfs();
return 0;
}
orZ%%%
tcl