水壶问题题解

这道题是经典的广度优先搜索（BFS）应用，目标是通过最少的操作在两个罐子中恰好得到指定容量的水。我们可以将每个状态看作是两个罐子的水量组合，通过BFS寻找从初始状态到目标状态的最短路径。

方法思路

1. 状态表示：使用结构体Node表示当前状态，包含两个罐子的水量x和y，以及记录操作序列的字符串op。

2. 状态转换：每个状态可以通过六种操作转换到新状态：

   • FILL(1)：将罐子1装满
   • FILL(2)：将罐子2装满
   • DROP(1)：将罐子1倒空
   • DROP(2)：将罐子2倒空
   • POUR(1,2)：将罐子1的水倒入罐子2
   • POUR(2,1)：将罐子2的水倒入罐子1

3. BFS实现：使用队列进行BFS，确保找到的路径是最短的。为避免重复处理状态，使用哈希表（通过数组模拟）记录已访问的状态。

解决代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <queue>
#include <map>
#include <math.h>
#include <string>
#include <string.h>
#include <bitset>

#define INF 0xfffffff
#define MAXN 100105

using namespace std;

struct Node{
    int x;
    int y;
    char op[100];
};

int a,b,c;
bool vis[MAXN];

void bfs() {
    queue<Node> q;
    memset(vis, false, sizeof(vis));

    Node start;
    start.x = 0;
    start.y = 0;
    memset(start.op,0,sizeof(start.op));
    vis[0] = true;

    q.push(start);

    Node node;
    Node tmp;
    while (!q.empty()) {
        node = q.front();
        q.pop();
        if(node.x==c||node.y==c){
            cout<<strlen(node.op)<<endl;
            for(int i = 0; node.op[i]!='\0'; i++){
                if(node.op[i]=='1')cout<<"FILL(1)\n";
                else if(node.op[i]=='2')cout<<"FILL(2)\n";
                else if(node.op[i]=='3')cout<<"DROP(1)\n";
                else if(node.op[i]=='4')cout<<"DROP(2)\n";
                else if(node.op[i]=='5')cout<<"POUR(1,2)\n";
                else if(node.op[i]=='6')cout<<"POUR(2,1)\n";
            }
            return;
        }
        // 操作1：装满罐子1
        if(!vis[a*1000+node.y]){
            tmp.x = a;
            tmp.y = node.y;
            strcpy(tmp.op,node.op);
            strcat(tmp.op,"1");
            q.push(tmp);
            vis[tmp.x*1000+tmp.y] = true;
        }
        // 操作2：装满罐子2
        if(!vis[node.x*1000+b]){
            tmp.x = node.x;
            tmp.y = b;
            strcpy(tmp.op,node.op);
            strcat(tmp.op,"2");
            q.push(tmp);
            vis[tmp.x*1000+tmp.y] = true;
        }
        // 操作3：倒空罐子1
        if(!vis[node.y]){
            tmp.x = 0;
            tmp.y = node.y;
            strcpy(tmp.op,node.op);
            strcat(tmp.op,"3");
            q.push(tmp);
            vis[tmp.x*1000+tmp.y] = true;
        }
        // 操作4：倒空罐子2
        if(!vis[node.x*1000]){
            tmp.x = node.x;
            tmp.y = 0;
            strcpy(tmp.op,node.op);
            strcat(tmp.op,"4");
            q.push(tmp);
            vis[tmp.x*1000+tmp.y] = true;
        }
        // 操作5：罐子1倒入罐子2
        tmp.y = node.x + node.y;
        if(tmp.y>b){
            tmp.y = b;
            tmp.x = node.x + node.y - b;
        }
        else tmp.x = 0;
        if(!vis[tmp.x*1000+tmp.y]){
            strcpy(tmp.op,node.op);
            strcat(tmp.op,"5");
            q.push(tmp);
            vis[tmp.x*1000+tmp.y] = true;
        }
        // 操作6：罐子2倒入罐子1
        tmp.x = node.x + node.y;
        if(tmp.x>a){
            tmp.x = a;
            tmp.y = node.x + node.y - a;
        }
        else tmp.y = 0;
        if(!vis[tmp.x*1000+tmp.y]){
            strcpy(tmp.op,node.op);
            strcat(tmp.op,"6");
            q.push(tmp);
            vis[tmp.x*1000+tmp.y] = true;
        }
    }
    cout<<"impossible";
}

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

代码解释

1. 结构体Node：存储两个罐子的水量x和y，以及操作序列op。

2. BFS初始化：初始状态为两个罐子都为空，将其加入队列并标记为已访问。

3. 状态处理：每次从队列取出一个状态，检查是否达到目标水量。如果是，则输出操作序列；否则，生成所有可能的新状态。

4. 生成新状态：对当前状态执行六种操作，每种操作生成一个新状态。检查新状态是否已访问，若未访问则加入队列。

5. 操作编码：使用数字1-6表示六种操作，存储在op字符串中，最后根据数字转换为对应的操作名称输出。

6. 无解处理：如果队列为空仍未找到目标状态，输出"impossible"。

该方法通过BFS确保找到的路径是最短的，利用哈希表避免重复处理状态，高效解决了问题。