8.罐子

标签：罐子 dist int DROP bfs 410 FILL

原题链接：https://www.acwing.com/problem/content/description/4225/

#include<bits/stdc++.h>
using namespace std;

struct Operator{
  int x,y;  
};
int a,b,c;
int dist[410][410];
string s[7]={"","FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
string pre[410][410];

void bfs()
{
    queue<Operator> q;
    memset(dist,-1,sizeof dist);
    q.push({0,0});
    dist[0][0]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t.x==c||t.y==c){
            cout<<dist[t.x][t.y]<<endl;
            for(auto i:pre[t.x][t.y])
            {
                cout<<s[i-'0']<<endl;
            }
            return;
        }
        int dx[7]={0,a,t.x,0,t.x,max(0,t.x-b+t.y),min(a,t.x+t.y)};
        int dy[7]={0,t.y,b,t.y,0,min(b,t.x+t.y),max(0,t.y-a+t.x)};
        for(int i=1;i<=6;i++)
        {
            if(dist[dx[i]][dy[i]]==-1){
                dist[dx[i]][dy[i]]=dist[t.x][t.y]+1;
                pre[dx[i]][dy[i]]=pre[t.x][t.y]+char(i+'0');
                q.push({dx[i],dy[i]});
            }
        }
    }
    cout<<"impossible"<<endl;
}

int main()
{
    cin>>a>>b>>c;
    bfs();
}

标签：罐子,dist,int,DROP,bfs,410,FILL
From： https://www.cnblogs.com/linearlearn/p/17280743.html