hdu1495 倒水bfs

题目链接：http://icpc.njust.edu.cn/Problem/Hdu/1495/

题意：给定三个杯子S,M,N,满足S=M+N，现在要求用最短的次数将S杯中的饮倒平分到两个杯子中。我们首先想到这个问题需要用搜索来解决，由于杯子没有刻度，所以每次倒水都是要将一个杯子中的水倒光或者将另一个杯子倒满，我们就这样在状态空间中搜索，直到check通过。由于是根据倒水的次数进行的层次搜索，所以最终确定的倒水次数一定是最少的次数。这道题竟然因为“NO”的“O”没有大写被卡，心态爆炸，什么是否能不写奇奇怪怪的bug ~T^T。

代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned int ui;

 typedef long long ll;

 typedef unsigned long long ull;

 #define pf printf

 #define mem(a,b) memset(a,b,sizeof(a))

 #define prime1 1e9+7

 #define prime2 1e9+9

 #define pi 3.14159265

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define scand(x) scanf("%llf",&x)

 #define f(i,a,b) for(int i=a;i<=b;i++)

 #define scan(a) scanf("%d",&a)

 #define dbg(args) cout<<#args<<":"<<args<<endl;

 #define inf 0x3f3f3f3f

 #define maxn 105

 int s,n,m,t;

 int ans=;

 int vol[];

 bool vis[maxn][maxn];//用两个杯子的容量即可确定三个被子的容量

 struct node{

     int v[],step;

     node(int a,int b,int c,int s){

         v[]=a,v[]=b,v[]=c,step=s;

     }

     node(){}

 };

 node cur,nxt;

 void pour(node &a,int i,int j)

 {

     int tmp=min(a.v[i],vol[j]-a.v[j]);

     a.v[i]-=tmp;

     a.v[j]+=tmp;

 }

 int bfs()

 {

     if(s%)return -;

     queue<node>q;

     q.push(node(s,,,));

     vis[s][]=;

     int k=s/;

     while(!q.empty())

     {

         cur=q.front();

         q.pop();

         if((cur.v[]==k&&cur.v[]==k)||(cur.v[]==k&&cur.v[]==k)||(cur.v[]==k&&cur.v[]==k))

         {

         //    cout<<cur.v[0]<<cur.v[1]<<cur.v[2]<<endl;

             return cur.step;

         }

         f(i,,)

             f(j,,)

             {

                 if(i==j)continue;

                 nxt=cur;

                 pour(nxt,i,j);

                 if(!vis[nxt.v[]][nxt.v[]])

                 {

                     vis[nxt.v[]][nxt.v[]]=;

                     nxt.step++;

                     q.push(nxt);

                 }

             }

     }

     return -;

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output.txt","w",stdout);

     std::ios::sync_with_stdio(false);

     while(scanf("%d%d%d",&s,&n,&m)&&s&&m&&n)

     {

             vol[]=s;

             vol[]=n;

             vol[]=m;

             mem(vis,false);

             ans=bfs();

             if(ans==-)

             {

                 pf("NO\n");

             }

             else pf("%d\n",ans);

     }

  }