题目描述

两个罐子倒水的问题，根据题意可以把两个罐子看成一个二维坐标，而这个坐标前前后后加起来有六种移动方法，这样可以把这道题看成一个简单的bfs求最短路问题，十分的amazing哈。但是有个问题需要给出最短的路径，这个借鉴了前辈的方法，用一个字符串一直存就可以了(看来前面两位的题解，膜拜大佬)，刚开始我用的pair，没办法存路径，后来就重写了个结构体来存了，其他就没什么了，bfs模板套就完了，废话不多说，上代码。

样例

输入样例：
3 5 4
输出样例：
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

C++ 代码

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
struct PII{
    int x;
    int y;
    string s;
};
string st[6]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int dis[110][110];
int a,b,c;
int bfs()
{
    memset(dis,-1,sizeof dis);
    queue<PII> Q;
    Q.push({0,0,""});
    dis[0][0]=0;
    while(Q.size())
    {
        auto au=Q.front();
        Q.pop();
        if(au.x==c||au.y==c)
        {
            cout<<dis[au.x][au.y]<<endl;
            //存好路径后遍历字符串输出就可以了，十分的方便哈
            for(auto a:au.s)
            {
                cout<<st[a]<<endl;
            }
            return 0;
        }
        //这里的操作是计算6种倒水的操作
        int t1=min(au.x,b-au.y);
        int t2=min(a-au.x,au.y);
        int vx[]={a-au.x,0,-au.x,0,-t1,t2};
        int vy[]={0,b-au.y,0,-au.y,t1,-t2};
        for(int i=0;i<6;i++)
        {
            int x=au.x+vx[i];
            int y=au.y+vy[i];
            if(dis[x][y]==-1)
            {
                dis[x][y]=dis[au.x][au.y]+1;
                //存路径
                char op=i;
                string s=au.s+op;
                Q.push({x,y,s});
            }
        }
    }
    cout<<"impossible"<<endl;
    return 0;
}
int main()
{
    cin>>a>>b>>c;
    bfs();
    return 0;
}