#include #include #include #include using namespace std; const int N=110; int n,m,k; int f[N][N];//f[i][j]表示i,j两个桶时能不能得到k int pre[N][N][3]; //0表示没有操作,1表示倒水,2表示清空 struct Node{ int x,y;//状态 int step; int last;//上一步操作 };

void bfs(){ queue q; memset(f,0,sizeof f); memset(pre,-1,sizeof pre); q.push({0,0,0,-1}); f[0][0]=1; while(q.size()){ auto t=q.front(); q.pop(); if(t.x==k||t.y==k){ printf("%d\n",t.step); int x=t.x,y=t.y; vector v; while(t.last!=-1){ v.push_back(t.last); int dx=pre[x][y][t.last],dy=t.last==1?y:x; x=dx,y=dy; t=Node({dx,dy,0,pre[x][y][0]}); } for(int i=v.size()-1;i>=0;i--){ if(v[i]==0) printf("FILL(%d)\n",i%2+1); else if(v[i]==1) printf("POUR(%d,%d)\n",i%2+1,3-i%2-v[i]); else printf("DROP(%d)\n",i%2+1); } return; } auto push=[&](int x,int y,int last){ if(f[x][y]) return; f[x][y]=1; pre[x][y][0]=t.x; pre[x][y][1]=t.y; pre[x][y][2]=last; q.push({x,y,t.step+1,last}); }; push(n,t.y,1); push(t.x,m,2); push(0,t.y,3); push(t.x,0,4); push(min(t.x+t.y,n),max(0,t.x+t.y-n),5); push(max(0,t.x+t.y-m),min(t.x+t.y,m),6); } puts("impossible"); }

int main(){ scanf("%d%d%d",&n,&m,&k); bfs(); return 0; }


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

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