#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> PII; const int N=110; int n,m,k; int pre[N][N];//pre[i][j]记录(i,j)点是从哪个点过来的 bool st[N][N];//判断当前状态是否访问过 string op[6]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"}; PII q[N*N];

void bfs(){ int hh=0,tt=0; q[0]={0,0};//初始状态两个桶都是空的 st[0][0]=true;//将初始状态设为已访问 while(hh<=tt){ auto t=q[hh++]; int a=t.x,b=t.y,c=a+b;//a,b是当前状态下两个桶中的水量,c是它们的和 if(a==k||b==k){ //如果当前状态满足条件k,输出答案 cout<<hh-1<<endl; vector ans; while(a||b){//从当前状态反推到初始状态 int p=pre[a][b];//找到上一个状态 ans.push_back(op[p]);//记录操作 auto t=q[p];//从队列中取出上一个状态 a=t.x,b=t.y;//更新a,b } reverse(ans.begin(),ans.end());//反转操作顺序 for(auto &t:ans) cout<<t<<endl;//输出操作 return; } //开始六种操作 //1、FILL(1) if(!st[n][b]){ st[n][b]=true; pre[n][b]=hh-1;//记录当前状态是从上一个状态通过哪种操作转移过来的 q[++tt]={n,b}; } //2、FILL(2) if(!st[a][m]){ st[a][m]=true; pre[a][m]=hh-1; q[++tt]={a,m}; } //3、DROP(1) if(!st[0][b]){ st[0][b]=true; pre[0][b]=hh-1; q[++tt]={0,b}; } //4、DROP(2) if(!st[a][0]){ st[a][0]=true; pre[a][0]=hh-1; q[++tt]={a,0}; } //5、POUR(1,2) int t=min(a,m-b);//倒出的水的数量,取决于当前两个桶的水量和容量 if(!st[a-t][b+t]){ st[a-t][b+t]=true; pre[a-t][b+t]=hh-1; q[++tt]={a-t,b+t}; } //6、POUR(2,1) t=min(n-a,b);//同理 if(!st[a+t][b-t]){ st[a+t][b-t]=true; pre[a+t][b-t]=hh-1; q[++tt]={a+t,b-t}; } } //如果到达这里,说明无法达成目标状态 cout<<"impossible"<<endl; }

int main(){ cin>>n>>m>>k; bfs(); return 0; }


原文地址: https://www.cveoy.top/t/topic/lBXc 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录