大致题意
告诉你两个壶的体积分别为A，B，开始两个壶都是空的，然后你可以把一个壶倒满，或者倒空，或者把一个壶里的水到给另一个壶直到另一个壶被倒满或者这个壶被倒空。 问你通过一系列的操作后是否可以使得其中一个壶里水的量为C，如果可以则输出最少操作次数，并输出相应的步骤，否则输出impossible.
思路
用pair储存壶的状态，BFS推出其他状态
map映射状态对应的步骤
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<queue>
#include<cstring>
#include<map>
#define ll long long
#define P pair<int,int>
using namespace std;
queue<P> que;
vector<int>::iterator it;
map<P, vector<int> > key;
int A,B,C;
int dis[110];
int flag[110][110];
int op[110][1000];
void opkey(int p){
if(p==1)printf("FILL(1)\n");
else if(p==2)printf("FILL(2)\n");
else if(p==3)printf("DROP(1)\n");
else if(p==4)printf("DROP(2)\n");
else if(p==5)printf("POUR(1,2)\n");
else if(p==6)printf("POUR(2,1)\n");
}
int bfs(int x,int y){
flag[x][y]=1;
P p;
que.push(P(x,y));
while(!que.empty()){
p=que.front();
que.pop();
if(flag[p.first][B]==0){
que.push(P(p.first,B));
for(it=key[p].begin();it!=key[p].end();it++)
key[P(p.first,B)].push_back(*it);
key[P(p.first,B)].push_back(2);
flag[p.first][B]=flag[p.first][p.second]+1;
}
if(flag[A][p.second]==0){
que.push(P(A,p.second));
flag[A][p.second]=flag[p.first][p.second]+1;
for(it=key[p].begin();it!=key[p].end();it++)
key[P(A,p.second)].push_back(*it);
key[P(A,p.second)].push_back(1);
}
if(flag[p.first][0]==0){
que.push(P(p.first,0));
flag[p.first][0]=flag[p.first][p.second]+1;
for(it=key[p].begin();it!=key[p].end();it++)
key[P(p.first,0)].push_back(*it);
key[P(p.first,0)].push_back(4);
}
if(flag[0][p.second]==0){
que.push(P(0,p.second));
flag[0][p.second]=flag[p.first][p.second]+1;
for(it=key[p].begin();it!=key[p].end();it++)
key[P(0,p.second)].push_back(*it);
key[P(0,p.second)].push_back(3);
}
if(p.first+p.second>B&&flag[p.first+p.second-B][B]==0){
que.push(P(p.first+p.second-B,B));
flag[p.first+p.second-B][B]=flag[p.first][p.second]+1;
dis[p.first+p.second-B]=min(dis[p.first+p.second-B],flag[p.first][p.second]+1);
for(it=key[p].begin();it!=key[p].end();it++)
key[P(p.first+p.second-B,B)].push_back(*it);
key[P(p.first+p.second-B,B)].push_back(5);
if(p.first+p.second-B==C){
cout<<dis[C]-1<<endl;
for(it=key[P(p.first+p.second-B,B)].begin();it!=key[P(p.first+p.second-B,B)].end();it++)
opkey(*it);
return 1;
}
}else if(p.first+p.second<=B&&flag[0][p.first+p.second]==0){
que.push(P(0,p.first+p.second));
flag[0][p.first+p.second]=flag[p.first][p.second]+1;
dis[p.first+p.second]=min(dis[p.first+p.second],flag[p.first][p.second]+1);
for(it=key[p].begin();it!=key[p].end();it++)
key[P(0,p.first+p.second)].push_back(*it);
key[P(0,p.first+p.second)].push_back(5);
if(p.first+p.second==C){
cout<<dis[C]-1<<endl;
for(it=key[P(p.first+p.second,0)].begin();it!=key[P(p.first+p.second,0)].end();it++)
opkey(*it);return 1;
}
}
if(p.first+p.second>A&&flag[A][p.first+p.second-A]==0){
que.push(P(A,p.first+p.second-A));
flag[A][p.first+p.second-A]=flag[p.first][p.second]+1;
dis[p.first+p.second-A]=min(dis[p.first+p.second-A],flag[p.first][p.second]+1);
for(it=key[p].begin();it!=key[p].end();it++)
key[P(A,p.first+p.second-A)].push_back(*it);
key[P(A,p.first+p.second-A)].push_back(6);
if(p.first+p.second-A==C){
cout<<dis[C]-1<<endl;
for(it=key[P(A,p.first+p.second-A)].begin();it!=key[P(A,p.first+p.second-A)].end();it++)
opkey(*it);return 1;
}
}else if(p.first+p.second<=A&&flag[p.first+p.second][0]==0){
que.push(P(p.first+p.second,0));
flag[p.first+p.second][0]=flag[p.first][p.second]+1;
dis[p.first+p.second]=min(dis[p.first+p.second],flag[p.first][p.second]+1);
for(it=key[p].begin();it!=key[p].end();it++)
key[P(p.first+p.second,0)].push_back(*it);
key[P(p.first+p.second,0)].push_back(6);
if(p.first+p.second==C){
cout<<dis[C]-1<<endl;
for(it=key[P(p.first+p.second,0)].begin();it!=key[P(p.first+p.second,0)].end();it++)
opkey(*it);return 1;
}
}
}
return 0;
}
int main()
{
for(int i=0;i<105;i++){
dis[i]=99999999;
}
scanf("%d%d%d",&A,&B,&C);
dis[A]=1;dis[B]=1;
if(C==A)cout<<"1"<<endl<<"FILL(1)";
else if(C==B)cout<<"1"<<endl<<"FILL(2)";
else {
if(bfs(0,0)==0)cout<<"impossible";
}
return 0;
}