罐子
↑ 题目链接
题目
给你两个罐子，容积分别为 \(A\) 升和 \(B\) 升。
现在，你可以进行如下三种操作：
FILL(i)，将罐子 \(i（1≤i≤2）\) 灌满水。
DROP(i)，将罐子 \(i（1≤i≤2）\) 清空。
POUR(i,j)，将罐子 \(i\) 中的水倒向罐子 \(j\) ，直到罐子 \(i\) 空了或罐子 \(j\) 满了为止。
请问，至少多少次操作后，可以使得其中一个罐子里恰好有 \(C\) 升水。
输入格式
共一行，三个整数 A,B,C。
输出格式
如果无解，则输出一行 impossible 即可。
否则，第一行输出一个整数，表示最少操作次数。
随后按顺序每行输出一个操作指令，格式参考题面。
数据范围
\(1≤A,B,C≤100,C≤max(A,B)\)
输入样例：
3 5 4
输出样例：
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
思路
通过 \(BFS\) 搜索 \(6\) 种状态，记录最短步数即可
代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
string op[]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int d[N][N];
int A,B,C;
struct Pos
{
int x,y;
string s;
};
void bfs()
{
memset(d,-1,sizeof d);
queue<Pos>q;
q.push({0,0,""});
d[0][0]=0;
while(q.size())
{
auto t=q.front();
q.pop();
if(t.x==C||t.y==C)
{
cout<<d[t.x][t.y]<<endl;//最少步数
for(auto x:t.s)//输出方案
{
cout<<op[x-'0']<<endl;
}
return;
}
int minx=min(t.x,B-t.y);
int miny=min(A-t.x,t.y);
//6种状态
int dx[]={A,t.x,0,t.x,t.x-minx,t.x+miny};
int dy[]={t.y,B,t.y,0,t.y+minx,t.y-miny};
for(int i=0;i<6;i++)
{
int a=dx[i],b=dy[i];
if(d[a][b]==-1)
{
d[a][b]=d[t.x][t.y]+1;
q.push({a,b,t.s+to_string(i)});
}
}
}
puts("impossible");
}
int main()
{
cin>>A>>B>>C;
bfs();
return 0;
}