UVA_10603 倒水问题隐式图搜索

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

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

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

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#define INF 1<<31;

using namespace std;

int vis[][][];

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>= ? q1 : -q1;

    q2=q2>= ? q2 : -q2;

    q3=q3>= ? 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<) c1=-c1;

    if (c2<) c2=-c2;

    if (c3<) c3=-c3;

    int ansc=min(c1,min(c2,c3));

    if (ansq<ansc) return ;

    if (ansq==ansc)

    {

        if (xq.minw<ans.minw) return ;

    }

    return ;

}

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]=;

      if (judge(x)) ans=x;

      node t1;

      int temp;

      if (x.a1>){

        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>){

        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>){

        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,,sizeof vis);

        node first;

        first.init(,,c);

        first.minw=;

        ans=first;

        ans.minw=INF;

        bfs(first);

        int tq[];

        tq[]=ans.a1;

        tq[]=ans.b1;

        tq[]=ans.c1;

        sort(tq+,tq+);

        int w;

        for (w=;w>=;w--)

        {

            if (tq[w]<=d) break;

        }

        printf("%d %d\n",ans.minw,tq[w]);

    }

    return ;

}

巴特西

UVA_10603 倒水问题隐式图搜索

最新文章

热门文章

巴特西

UVA_10603 倒水问题 隐式图搜索

最新文章

热门文章

UVA_10603 倒水问题隐式图搜索