HDU1495 非常可乐

解题思路：简单的宽搜，见代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 105;
int S, n, m, cap[3], vis[maxn][maxn];

struct node{
    int v[3];//每个子装的水
    int cnt; //倒水的次数
    bool friend operator < (node A, node B){
        return A.cnt > B.cnt; //cnt越小，优先级越高
    }
}s, e;

priority_queue<node> q; //优先队列

int bfs()
{
    while(!q.empty()) q.pop();
    q.push(s);

    while(!q.empty())
    {
       s = q.top(); q.pop();
      // printf("s.cnt = %d
", s.cnt); //太大意，因为这行没注释，WA了一发
        
        //n杯子和s杯子各有一半可乐时返回倒水次数
       if(s.v[0] == S / 2 && s.v[2] == S / 2) return s.cnt;
       
       //i杯子往j杯子里面倒水
       for(int i = 0; i < 3; i++)
       for(int j = 0; j < 3; j++)
       {
           if(i == j) continue; //不能往自己的杯子倒水
           //如果i杯子是空的或者j杯子已满，则不用倒水
           if(s.v[i] == 0 || s.v[j] == cap[j]) continue;
            
           int t = min(s.v[i], cap[j] - s.v[j]); //自己思考这一步
           e = s; //这步不能忘了
           e.v[i] = s.v[i] - t, e.v[j] = s.v[j] + t, e.cnt = s.cnt + 1;
           if(!vis[e.v[0]][e.v[1]]) //没访问过
           {
               vis[e.v[0]][e.v[1]] = 1; //标记为已经访问
               q.push(e);
           }
        }
    }
    return -1; //若没有符合条件的，则返回-1
}

int main()
{
    while(~scanf("%d %d %d", &S, &n, &m) && (S || n || m))
    {
        if(S % 2) //s为奇数，则不可能均分
        {
            printf("NO
");
            continue;
        }

        if(n == m) //n等于m时，直接把一个杯子倒满即可
        {
            printf("1
");
            continue;
        }
        int tmp;
        //初始化n为更大的杯子
        if(m > n) tmp = n, n = m, m = tmp;
        memset(vis, 0, sizeof(vis));

        cap[0] = n, cap[1] = m, cap[2] = S;
        s.v[0] = 0, s.v[1] = 0, s.v[2] = S, s.cnt = 0;
        vis[0][0] = 1; 

        int ans = bfs();

        if(ans == -1) printf("NO
");
        else printf("%d
", ans);
    }
    return 0;
}