hdu 1495 非常可乐(bfs)

#include <cstdio>
#include <map>
#include <iostream>
#include<cstring>
#include<bits/stdc++.h>
#define ll long long int
#define M 6
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1};
int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
int v[3],ans;
struct node{
    int a[3]; //当前3杯水的容量
    int step;
};
node t;
queue<node> q;
bool vis[107][107][107];
void pour(int from,int to){
    //很巧妙的倒水算法，行数最少
    int temp=t.a[from]+t.a[to];
    if(temp>=v[to]) t.a[to]=v[to];
    else t.a[to]=temp;
    t.a[from]=temp-t.a[to];
}
void bfs(){
    while(!q.empty()){
        node temp=q.front();
        q.pop();
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                for(int k=0;k<3;k++){
                if(i==j||i==k||k==j)
                continue;
                if(temp.a[i]==temp.a[j]&&!temp.a[k]){
                    ans=temp.step;
                    return ;
                }
            }
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++){
                if(i==j)
                continue;
                t=temp;
                pour(i,j); //从i到给j
                if(!vis[t.a[0]][t.a[1]][t.a[2]]){
                    t.step++;
                    vis[t.a[0]][t.a[1]][t.a[2]]=1;
                    q.push(t);
                }
            }
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>v[0]>>v[1]>>v[2]){
        if(!v[0]&&!v[1]&&!v[2])
        break;
        memset(vis,0,sizeof(vis));
        if(v[0]%2!=0)
        cout<<"NO"<<endl;
        else{
            node t; t.a[0]=v[0]; t.a[1]=0; t.a[2]=0; t.step=0;
            vis[v[0]][0][0]=1;
            q.push(t);
            ans=inf;
            bfs();
            if(ans!=inf)
            cout<<ans<<endl;
            else cout<<"NO"<<endl;
            while(!q.empty())
            q.pop();
        }
    }
}