广搜解题：倒水问题

题目描述

给你两个容量为 n 和 m 的水桶和无限多的水，两个桶初始为空，现在需要盛出容量为 k 的水，由于水桶没有刻度，你只能进行如下几种操作
1、 FILL x 表示将第 x 个水桶装满，x 为 1 或 2
2、 DROP x 表示将第 x 个水桶清空，x 为 1 或 2
3、 POUR x y 表示将第 x 个桶的水全部倒入 y 桶，x 空了或 y 满了停止，x，y 为 1 或 2
问最少需要的操作次数及操作过程，若有多种操作方法可以完成，输出任意一种即可。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3 5 4

样例输出 #1

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

提示

0<n,m,k<100

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N = 110;

typedef struct Node
{
    int a,b,d;
    string path;
}node;

struct cmp
{
    bool operator()(node &a,node &b)
    {
        return a.d>b.d;
    }
};

int n,m,k;
bool vis[N][N];
priority_queue<node,vector<node>,cmp> q;

void bfs()
{
    node s;
    s.a=0,s.b=0,s.d=0;
    q.push(s);
    while(q.size())
    {
        node t=q.top();
        q.pop();
        if(vis[t.a][t.b])
            continue;
        vis[t.a][t.b]=true;
        if(t.a==k||t.b==k)
        {
            cout<<t.d<<endl<<t.path;
            return;
        }
        node a,b,c,d,e;
        a=t,b=t,c=t,d=t,e=t;
        if(!vis[n][t.b])
        {
            a.a=n,a.path+="FILL(1)\n";
            a.d=t.d+1;
            q.push(a);
        }
        if(!vis[t.a][m])
        {
            b.b=m,b.path+="FILL(2)\n";
            b.d=t.d+1;
            q.push(b);
        }
        if(!vis[0][t.b])
        {
            c.a=0,c.path+="DROP(1)\n";
            c.d=t.d+1;
            q.push(c);
        }
        if(!vis[t.a][0])
        {
            d.b=0,d.path+="DROP(2)\n";
            d.d=t.d+1;
            q.push(d);
        }
        if(!vis[min(t.a+t.b,n)][max(0,t.b-t.a)]) 
        { 
            e.a=min(t.a+t.b,n),e.b=max(0,t.b-t.a); 
            e.path+="POUR(1,2)\n"; 
            e.d=t.d+1; 
            q.push(e); 
        } 
        if(!vis[max(0,t.a-t.b)][min(t.b+t.a,m)]) 
        { 
            e.a=max(0,t.a-t.b),e.b=min(t.b+t.a,m); 
            e.path+="POUR(2,1)\n"; 
            e.d=t.d+1; 
            q.push(e); 
        } 
    }
    cout<<"impossible";
}

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