一、题目描述

原题链接

给你两个罐子，容积分别为 $A$ 升和 $B$ 升。

现在，你可以进行如下三种操作：

 1. FILL(i)，将罐子 $i（1 \leq i \leq 2）$ 灌满水。
 2. DROP(i)，将罐子 $i（1 \leq i \leq 2）$ 清空。
 3. POUR(i,j)，将罐子 $i$ 中的水倒向罐子 $j$，直到罐子 $i$ 空了或 罐子 $j$ 满了为止。

请问，至少多少次操作后，可以使得其中一个罐子里恰好有 $C$ 升水。

二、解题思路

  首先看到至少多少次操作，可以确定本题的解法为 BFS，重点在于怎么建立模型。题目中规定两个罐子只需要一个达到 $C$ 升即可，在满足条件时无非就被拆成了三种情况：第一个罐子到达第二个罐子没到达、第一个罐子没到达第二个罐子到达、两个罐子都到达，这样就就会发现两者可以直接联系为一个二元组 $(i,j)$，此时也就将其完美的抽象为一个二维坐标，而进行的三种操作实际可以分成 $6$ 种情况，因此问题就转化为：给你一个点，初始情况下点在 $(0,0)$ 为止，你可以执行 $6$ 种操作，请找到最短的路线使得该点到达 $x = C$ 或 $y = C$ 这条直线上。

  将问题转化后接下来就是传统的 BFS 搜索，使用的就是走迷宫问题的模型，其中需要注意的，因为最后要把路线打印出来，所以最好的方法是直接建立一个结构体，结构体中除了传统的 $x$ 和 $y$，多维护一个指令 $s$，用来记录在这过程中都执行了哪些指令，当搜到答案时直接输出即可。

三、AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;
typedef long long ll;

const int N = 110;

string st[6]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};

int a,b,c;
int dis[N][N];

struct Node{
    int x;
    int y;
    string s;//当前状态执行过的指令
};

void bfs(){
    memset(dis,-1,sizeof dis);
    queue<Node> q;
    q.push({0,0,""});
    dis[0][0] = 0;
    while(!q.empty()){
        Node u = q.front();
        q.pop();
        if(u.x == c || u.y == c){
            cout << dis[u.x][u.y] << endl;
            for(int i = 0;i<u.s.size();i++){
                cout << st[u.s[i]] << endl;
            }
            return;
        }
        //枚举可以走的6种方向
        int t1 = min(u.x,b - u.y);//向b中要加的水
        int t2 = min(u.y,a - u.x);//向a中要加的水
        int dx[6] = {a - u.x,0,-u.x,0,-t1,t2};
        int dy[6] = {0,b - u.y,0,-u.y,t1,-t2};
        for(int i = 0;i<6;i++){
            int xx = u.x + dx[i];
            int yy = u.y + dy[i];
            if(dis[xx][yy] == -1){
                dis[xx][yy] = dis[u.x][u.y] + 1;
                char op = i;
                string s = u.s + op;
                q.push({xx,yy,s});
            }
        }
    }
    cout << "impossible" << endl;
}

int main()
{
    cin >> a >> b >> c;
    bfs();
    system("pause");
    return 0;
}