[DeepJudge P1001] 倒水问题 题解

总共有6种可能的操作：

1. x壶向y壶倒水
2. y壶向x壶倒水
3. 将x壶倒空
4. 将x壶倒满
5. 将y壶倒空
6. 将y壶倒满

其中，x壶向y壶倒水分为两种情况：

• x壶先被倒空而y壶未满
• y壶先被倒满而x壶未空

同样地，y壶向x壶倒水也分为两种情况：

• y壶先被倒空而x壶未满
• x壶先被倒满而y壶未空

我们暴力尝试这6种可能的操作，去掉重复的状态，使用BFS即可得出最小步数。代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
int step[110][110];
int Qx[11000], Qy[11000];
int Qhead=0, Qtail=0;
int x, y, z;
void push_back(int nx, int ny, int nt){
    if(nx<0 || nx>x || ny<0 || ny>y || step[nx][ny]>=0) return;
    step[nx][ny] = nt;
    Qx[Qtail] = nx;
    Qy[Qtail] = ny;
    Qtail++;
}
bool bfs(){
    while(Qhead<Qtail){
        int nx=Qx[Qhead], ny=Qy[Qhead], nt=step[nx][ny];
        if(nx==z || ny==z){
            printf("%d\n",nt);
            return true;
        }
        push_back(x,ny,nt+1);
        push_back(0,ny,nt+1);
        push_back(nx,y,nt+1);
        push_back(nx,0,nt+1);
        if(nx>y-ny) push_back(nx-(y-ny),y,nt+1); 
        else push_back(0,ny+nx,nt+1);
        if(ny>x-nx) push_back(x,ny-(x-nx),nt+1); 
        else push_back(nx+ny,0,nt+1);
        Qhead++;
    }
    return false;
}
int main(){
    memset(step, -1, sizeof(step));
    scanf("%d%d%d", &x, &y, &z);
    push_back(0, 0, 0);
    if(!bfs()) printf("impossible\n");
    return 0;
}