#include #include #include using namespace std; const int N=110; int fa[N][N]; bool st[N][N]; struct node{ int x,y; string str; node(int a,int b,string c):x(a),y(b),str(c){}; }; int a,b,c; void output(int x,int y) { if(!x&&!y) return; int fx=fa[x][y]/100,fy=fa[x][y]%100; output(fx,fy); if(fx==x&&fy==y) return; if(fx==0&&fy==y) cout<<'DROP(1)'<<endl; else if(fx==x&&fy==0) cout<<'DROP(2)'<<endl; else if(fx==x&&fy==y) cout<<'POUR(2,1)'<<endl; else if(fx==y&&fy==x) cout<<'POUR(1,2)'<<endl; else if(fx==0&&fy!=y) cout<<'FILL(1)'<<endl; else if(fx!=x&&fy==0) cout<<'FILL(2)'<<endl; } void bfs() { queue q; q.push(node(0,0,'')); st[0][0]=true; while(!q.empty()) { auto t=q.front(); q.pop(); if(t.x==c||t.y==c) { cout<<t.str.size()/5<<endl<<t.str<<endl; return; } if(!st[a][t.y]) //第一个桶装满 { st[a][t.y]=true; fa[a][t.y]=t.x100+t.y; q.push(node(a,t.y,t.str+'FILL(1) ')); } if(!st[t.x][b]) //第二个桶装满 { st[t.x][b]=true; fa[t.x][b]=t.x100+t.y; q.push(node(t.x,b,t.str+'FILL(2) ')); } if(!st[0][t.y]) //第一个桶倒空 { st[0][t.y]=true; fa[0][t.y]=t.x100+t.y; q.push(node(0,t.y,t.str+'DROP(1) ')); } if(!st[t.x][0]) //第二个桶倒空 { st[t.x][0]=true; fa[t.x][0]=t.x100+t.y; q.push(node(t.x,0,t.str+'DROP(2) ')); } if(t.x+t.y>b&&!st[t.x-(b-t.y)][b]) //第一个桶往第二个桶倒水 { st[t.x-(b-t.y)][b]=true; fa[t.x-(b-t.y)][b]=t.x100+t.y; q.push(node(t.x-(b-t.y),b,t.str+'POUR(1,2) ')); } else if(t.x+t.y<=b&&!st[0][t.x+t.y]) //第二个桶往第一个桶倒水 { st[0][t.x+t.y]=true; fa[0][t.x+t.y]=t.x100+t.y; q.push(node(0,t.x+t.y,t.str+'POUR(2,1) ')); } if(t.x+a<=a+b&&(!st[t.x+a][t.y])) //第一个桶往第二个桶倒水 { st[t.x+a][t.y]=true; fa[t.x+a][t.y]=t.x100+t.y; q.push(node(t.x+a,t.y,t.str+'POUR(1,2) ')); } else if(t.x+a>a+b&&(!st[a][t.x-(b-t.y)])) //第二个桶往第一个桶倒水 { st[a][t.x-(b-t.y)]=true; fa[a][t.x-(b-t.y)]=t.x100+t.y; q.push(node(a,t.x-(b-t.y),t.str+'POUR(2,1) ')); } } cout<<'impossible'<<endl; } int main() { cin>>a>>b>>c; bfs(); if(c!=0) output(a,b); return 0; }


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

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