#include #include #include #include using namespace std; const int N=110,M=10010; int n,m,k,ans; int st[N][N],d[N][N],pre[N][N][2];//pre用来记录前驱,最后输出路径 struct node{ int a,b; // a表示左边,b表示右边 int d; //表示当前状态的步数 }path[M]; bool vis[N][N]; int dx[6]={-1,1,0,0,0,0},dy[6]={0,0,-1,1,0,0}; //dx,dy表示在一个桶里进行的操作 //FILL,DRIP表示在一个桶里水的状态,用于记录路径 string op[6]={'FILL(1)','FILL(2)','DROP(1)','DROP(2)','POUR(1,2)','POUR(2,1)'}; string FILL[2]={'FILL(1)','FILL(2)'},DRIP[2]={'DROP(1)','DROP(2)'}; void bfs(){ queue<pair<int,int>>q; q.push({0,0}); d[0][0]=0; vis[0][0]=1; while(q.size()){ auto t=q.front(); q.pop(); int a=t.first,b=t.second; if(a==k||b==k){ ans=d[a][b]; break; } for(int i=0;i<6;i++){ int na=a+dx[i],nb=b+dy[i]; if(na>=0&&na<=n&&nb>=0&&nb<=m&&!vis[na][nb]){ vis[na][nb]=1; d[na][nb]=d[a][b]+1; st[na][nb]=i; pre[na][nb][0]=a,pre[na][nb][1]=b;//记录前驱 q.push({na,nb}); } } } } int main(){ cin>>n>>m>>k; bfs(); if(ans==-1){ puts('impossible'); return 0; } int cnt=0; while(k){ int a=pre[k][0][0],b=pre[k][0][1],c=st[k][0]; if(c<4)path[cnt++]={a,b,d[k][0],c}; k=a; } reverse(path,path+cnt); cout<<ans<<endl; for(int i=0;i<cnt;i++){ int a=path[i].a,b=path[i].b,c=path[i].d,d=path[i].d; if(c<4)cout<<op[c]<<endl; else cout<<op[c]<<endl; } return 0; }


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

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