UVA_10603 倒水问题 隐式图搜索

这道题目是刘汝佳白书上的例题，没有LRJ在白书上提到的划归为搜索问题，还真是一时难以想到好的解法。即三个瓶子，任意的一个状态都是一个节点，最后就划归为一个搜索问题。

由于题目数据量不大，三个杯子容量都不超过200，所以用个vis三维数组保存下访问过得状态以达到剪枝的目的，不过我在想数据量稍微大一点，这个数组就开不下了，同时搜索时间将大大增加。。。所以面对大数据的时候有没有更好的方法，我暂时还没想到。

代码写得超级挫，每个状态的转化都是手动敲的，好像可以用一个函数统一解决，当时写的时候就比较急，就直接手敲了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define INF 1<<31;
using namespace std;
int vis[205][205][205];
int a,b,c,d;
struct node{
    int a1,b1,c1;
    int minw;
    void init(int a,int b,int c)
    {
        a1=a;b1=b;c1=c;
    }
};
node ans;
bool judge(node xq)
{
    int q1,q2,q3;
    q1=xq.a1-d;
    q2=xq.b1-d;
    q3=xq.c1-d;

    q1=q1>=0 ? q1 : -q1;
    q2=q2>=0 ? q2 : -q2;
    q3=q3>=0 ? q3 : -q3;
    int ansq=min(q1,min(q2,q3));
    int c1,c2,c3;
    c1=ans.a1-d;
    c2=ans.b1-d;
    c3=ans.c1-d;
    if (c1<0) c1=-c1;
    if (c2<0) c2=-c2;
    if (c3<0) c3=-c3;
    int ansc=min(c1,min(c2,c3));

    if (ansq<ansc) return 1;
    if (ansq==ansc)
    {
        if (xq.minw<ans.minw) return 1;
    }
    return 0;

}
void bfs(node xq)
{
    queue<node>q;
    q.push(xq);
    while (!q.empty())
    {
      node x=q.front();
      q.pop();
      if (vis[x.a1][x.b1][x.c1]) continue;
      vis[x.a1][x.b1][x.c1]=1;
      if (judge(x)) ans=x;
      node t1;
      int temp;
      if (x.a1>0){
        t1=x;
        if (x.b1<b){
            temp=min(b-x.b1,x.a1);
            t1.a1-=temp;
            t1.b1+=temp;
            t1.minw+=temp;
            q.push(t1);
        }
        t1=x;
        if (x.c1<c){
            temp=min(c-x.c1,x.a1);
            t1.a1-=temp;
            t1.c1+=temp;
            t1.minw+=temp;
            q.push(t1);
        }
      }
      if (x.b1>0){
        t1=x;
        if (x.a1<a)
        {
            temp=min(a-x.a1,x.b1);
            t1.b1-=temp;
            t1.a1+=temp;
            t1.minw+=temp;
            q.push(t1);
        }
        t1=x;
        if (x.c1<c){
            temp=min(c-x.c1,x.b1);
            t1.b1-=temp;
            t1.c1+=temp;
            t1.minw+=temp;
            q.push(t1);
        }
      }
    if (x.c1>0){
        t1=x;
        if (x.a1<a){
            temp=min(a-x.a1,x.c1);
            t1.c1-=temp;
            t1.a1+=temp;
            t1.minw+=temp;
            q.push(t1);
        }
        t1=x;
        if (x.b1<b){
            temp=min(b-x.b1,x.c1);
            t1.c1-=temp;
            t1.b1+=temp;
            t1.minw+=temp;
            q.push(t1);
        }
      }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        memset(vis,0,sizeof vis);
        node first;
        first.init(0,0,c);
        first.minw=0;
        ans=first;
        ans.minw=INF;
        bfs(first);
        int tq[3];
        tq[1]=ans.a1;
        tq[2]=ans.b1;
        tq[3]=ans.c1;
        sort(tq+1,tq+4);
        int w;
        for (w=3;w>=1;w--)
        {
            if (tq[w]<=d) break;
        }
        printf("%d %d
",ans.minw,tq[w]);

    }
    return 0;
}