uva 10603 - Fill

点击打开链接

题目所属： 隐式图的搜索

题目意思： 有三个容器大小为 a b c 刚开始 a b都是空的 c是满的，现在给定一个d 大小的水量 ，要求我么找到最小的倒水总量使得有一个容器的水量为 d，如果找不到那么就用d'代替d（d' < d）直到能够找到有一个容器的水量为 d为止，最后输出 最小的倒水总量和 d'

解题思路： 倒水条件：假设是a倒入b中，那么必须要有a被倒空或 b 被倒满。
经典的倒水问题，只是结果是要我们输出最小的倒水总量而不是次数，这个需要注意。我们知道对于三个容器而言，里面就是水装的多不多，那么我么就知道这个容器的状态就是水的多少，那么开始的状态就是（0 ， 0 ， c），我们还知道如果容器a有水那么它可以选择倒到b 和 c ，其它类似。那么这个解空间树就是一个多叉树，我们就可以通过BFS进行搜索，搜索每一状态，那么我么只要开一个结构体里面放三个容器的水量和当前状态的最小倒水总量，那么只要找到有一个容器的水量为d，那么我们就可以去更新ans（判断ans是否大于当前的minsum）。如果没办法倒出d的水量，那么我么就用一个循环往下搜索直到找到d'。最后输出ans 和 d

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;
#define MAXN  210

int t , ans;
int vis[MAXN][MAXN][MAXN];//标记状态是否出现过
int jugs[3] , d;
struct Node{//结构体存储三个容器的水量和当前状态的最小倒水总量
    int v[3];
    int minsum;
};
queue<Node>q;

void Bfs(){
    while(!q.empty())
        q.pop();
    memset(vis , 0 , sizeof(vis));
    ans = 999999999;//初始化为无穷大
    vis[0][0][jugs[2]] = 1; //初始状态
    Node tmp;
    tmp.v[0] = 0;
    tmp.v[1] = 0;
    tmp.v[2] = jugs[2];
    tmp.minsum = 0;
    q.push(tmp);//第一个状态先入对列
    while(!q.empty()){
        Node tmp = q.front();
        q.pop();
        for(int i = 0 ; i < 3 ; i++){//枚举三个容器
            if(tmp.v[i] == d){//只要有一个容器的水量为d就判断并且跳出该次的循环
                if(ans > tmp.minsum)
                    ans = tmp.minsum;
                break;
            }
            else{ 
                for(int j = 0 ; j < 3 ; j++){//这个就是去判断容器v[i]能不能够倒水到v[j]。
                    if(i != j){//倒水前提是不同一个容器
                        Node Tmp = tmp;
                        if(tmp.v[i] && jugs[j] - tmp.v[j]){//如果v[i]有水并且v[j]有剩余的空间可以存水才满足
                            int min = tmp.v[i] < jugs[j] - tmp.v[j] ? tmp.v[i] : jugs[j] - tmp.v[j];//找到两者中的最小这样才能满足倒水的条件
                            Tmp.minsum += min;//当前倒水量加上min
                            Tmp.v[i] -= min;//容器相应减少水量
                            Tmp.v[j] += min;//容器相应减少水量
                            if(!vis[Tmp.v[0]][Tmp.v[1]][Tmp.v[2]]){//如果这个状态没出现过才push进队列
                                vis[Tmp.v[0]][Tmp.v[1]][Tmp.v[2]] = 1;
                                q.push(Tmp);
                            }
                        }
                    }
                }
            }
        }
    }
}

int main(){
    scanf("%d" , &t);
    while(t--){
        scanf("%d%d%d%d" , &jugs[0] , &jugs[1] , &jugs[2] , &d);
        Bfs();
        if(ans == 999999999){////如果需要继续Bfs
            while(1){
                    d--;//向下搜索
                    Bfs();
                    if(ans != 999999999) break;//只要找到满足就退出
            }
        }
        printf("%d %d\n" , ans , d);//最后输出结果
    }
    return 0;
}