广搜算法解决倒水问题：C++ 代码实现

问题描述:

给你两个容量为 n 和 m 的水桶和无限多的水，两个桶初始为空。现在需要盛出容量为 k 的水。由于水桶没有刻度，你只能进行如下几种操作：

FILL(x) 表示将第 x 个水桶装满，x 为 1 或 2
DROP(x) 表示将第 x 个水桶清空，x 为 1 或 2
POUR(x, y) 表示将第 x 个桶的水全部倒入 y 桶，x 空了或 y 满了停止，x, y 为 1 或 2

问最少需要的操作次数及操作过程，若有多种操作方法可以完成，输出任意一种即可。

输入格式:

一行三个整数 n, m, k。

输出格式:

第一行一个整数 x 表示最少操作次数。接下来 x 行，每行一个操作若无法做到输出 'impossible'

样例 #1:

样例输入 #1

3 5 4

样例输出 #1

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

C++ 代码实现:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;
const int INF = 0x3f3f3f3f;

struct Node
{
    int x, y;
    bool st[N][N];          //记录状态，避免重复
    int path[N][2];         //记录转移路径
};

int n, m, k;
bool st[N][N];
int path[N][2];
bool vis[N][N];
queue<Node> q;

void bfs()
{
    Node start;
    start.x = 0, start.y = 0;
    memset(start.st, 0, sizeof start.st);
    memset(start.path, -1, sizeof start.path);
    q.push(start);
    st[0][0] = true;

    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        if(t.x == k || t.y == k)    //满足条件
        {
            int cnt = 0;
            while(t.path[cnt][0] != -1) cnt ++ ;
            cout << cnt << endl;
            for(int i = cnt - 1; i >= 0; i -- )
            {
                if(t.path[i][0] == 1 && t.path[i][1] == 1) cout << "FILL(1)" << endl;
                else if(t.path[i][0] == 2 && t.path[i][1] == 2) cout << "FILL(2)" << endl;
                else if(t.path[i][0] == 1 && t.path[i][1] == 2) cout << "POUR(1,2)" << endl;
                else if(t.path[i][0] == 2 && t.path[i][1] == 1) cout << "POUR(2,1)" << endl;
                else if(t.path[i][0] == 1) cout << "DROP(1)" << endl;
                else if(t.path[i][0] == 2) cout << "DROP(2)" << endl;
            }
            return;
        }

        if(!t.st[n][t.y])   //将 A 倒满
        {
            Node k = t;
            k.st[n][t.y] = true;
            k.path[0][0] = 1, k.path[0][1] = 1;
            for(int i = 0; i < n; i ++ )
            {
                if(!t.st[i][t.y])
                {
                    k.st[i][t.y] = true;
                    k.path[1][0] = 1, k.path[1][1] = 2;
                    k.path[2][0] = -1, k.path[2][1] = -1;
                    q.push(k);
                    k.st[i][t.y] = false;
                }
            }
        }

        if(!t.st[t.x][m])   //将 B 倒满
        {
            Node k = t;
            k.st[t.x][m] = true;
            k.path[0][0] = 2, k.path[0][1] = 2;
            for(int i = 0; i < m; i ++ )
            {
                if(!t.st[t.x][i])
                {
                    k.st[t.x][i] = true;
                    k.path[1][0] = 2, k.path[1][1] = 1;
                    k.path[2][0] = -1, k.path[2][1] = -1;
                    q.push(k);
                    k.st[t.x][i] = false;
                }
            }
        }

        if(!t.st[0][t.y])  //将 A 清空
        {
            Node k = t;
            k.st[0][t.y] = true;
            k.path[0][0] = 1, k.path[0][1] = -1;
            q.push(k);
        }

        if(!t.st[t.x][0])  //将 B 清空
        {
            Node k = t;
            k.st[t.x][0] = true;
            k.path[0][0] = 2, k.path[0][1] = -1;
            q.push(k);
        }

        if(t.x + t.y > n && !t.st[n][t.y - (n - t.x)])  //将 A 倒入 B
        {
            Node k = t;
            k.st[n][t.y - (n - t.x)] = true;
            k.path[0][0] = 1, k.path[0][1] = 2;
            q.push(k);
        }

        if(t.x + t.y > m && !t.st[t.x - (m - t.y)][m])  //将 B 倒入 A
        {
            Node k = t;
            k.st[t.x - (m - t.y)][m] = true;
            k.path[0][0] = 2, k.path[0][1] = 1;
            q.push(k);
        }
    }
    cout << "impossible" << endl;
}

int main()
{
    cin >> n >> m >> k;
    bfs();
    return 0;
}

代码解释:

使用结构体 Node 来存储状态信息，包括两个桶的水量 x, y，一个二维数组 st 用来标记是否访问过该状态，一个二维数组 path 用来记录到达该状态的路径，即操作序列。
使用队列 q 来进行广度优先搜索，每次从队列中取出一个节点，判断该节点是否满足目标条件（即某个桶的水量等于 k）。
如果满足目标条件，则输出操作序列。
否则，根据当前节点的状态，进行所有可能的操作，并将操作后的状态加入队列。
在添加新状态时，需要检查该状态是否已经访问过，避免重复搜索。

总结:

广度优先搜索（BFS）算法是一种高效的图搜索算法，可以用于解决倒水问题。通过使用 Node 结构体和队列 q，可以方便地实现 BFS 算法，并找到满足目标条件的最少操作次数和操作序列。

希望本文的介绍和代码示例可以帮助您更好地理解广搜算法在解决倒水问题中的应用。