UVAOJ 10603 - Fill

gistfile1.txt

#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

int state[3];//每个瓶子的状态。
int vol[3];//每个瓶子里的水量
bool vis[200][200][200];
bool flag;
int minvol,maxmin;//要找的解
int a,b,c,d;

void dfs(int tot){
    for(int i = 0; i < 3; i++){//每次状态更行之后，查看是否有符合终止条件的。
        if(state[i] == d){//在某次的搜索中，若刚好有瓶子中的水为d
                maxmin = d;//这个不能丢弃。
                //cout<<flag<<":"<<d<<":"<<state[i]<<endl;
                if(!flag) minvol = tot;//如果第第一次找到解
                else if(tot < minvol) minvol = tot;//如果不是第一次找到解，则只有找到更小的才更新。
                flag = true;
                //cout<<minvol<<endl;
        }
        else if(!flag && state[i] < d){//在没找到的时候，而且此时瓶子里的水小于目标值d.
            if(d - state[i] < maxmin){//找到距离目标值最近的maxmin
                maxmin = d - state[i];//若新的最近值小于旧的，则更新。
                minvol = tot;//同时更新总量minvol.
                //cout<<minvol<<endl;
            }
            else if(d - state[i] == maxmin && tot < minvol)//若最近的值相同，但是此时的总量变小了，则更新总量。
                minvol = tot;
        }
    }
    for(int i = 0; i < 3; i++){//从i往j里面倒水，不过要先判断是否能倒。也就是一共有6种状态
        for(int j = 0; j < 3; j++){
            if(i!= j && state[i] && state[j] != vol[j]){
                int tmpi = state[i], tmpj = state[j];//记录旧的状态

                //int w = vol[j] - state[j];
                int w;
                if(state[i] >= vol[j] - state[j]){//如果要倒的水大于被倒的容量。
                    w = vol[j] - state[j];//真正可以倒的水。
                    state[i] -= w;
                    state[j] = vol[j];//被倒的水肯定满了。
                    //cout<<state[i]<<":"<<state[j]<<endl;
                }
                else{
                    /*w = state[i];这里是之前的代码，可以看到我把顺序给弄错了，导致结果错误
                    state[i] = 0;
                    state[j] += state[i];*/
                    state[j] += state[i];//先把水倒进state[j]中。
                    w = state[i];//真正可以倒的水。
                    state[i] = 0;//倒水的那个瓶子清空
                }
                if(!vis[state[0]][state[1]][state[2]]){//如果这个状态没有出现过。如果这个状态出现过（这是不可避免的，
                        //不过好在暴力搜索的时间能容忍），则上面倒水就是白忙活了...
                    vis[state[0]][state[1]][state[2]] = true;
                    dfs(tot + w);
                    vis[state[0]][state[1]][state[2]] = false;
                }//
                state[i] = tmpi;
                state[j] = tmpj;
            }
        }
    }
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>a>>b>>c>>d;
        vol[0] = a,vol[1] = b,vol[2] = c;//各个瓶子的容量
        state[0] = 0;state[1] = 0;state[2] = c;//各个瓶子的初试状态，前两个为空，第3个满。
        memset(vis,0,sizeof(vis));
        minvol = 100000000;maxmin = 100000000;//maxmin是当找不到有刚好等于d的时候，距离d的最近的距离。
        flag = false;//初始化为没找到解
        vis[0][0][c] = true;//初试状态的访问标识位为真。
        dfs(0);
        if(flag) cout<<minvol<<" "<<maxmin<<endl;//如果找到了，maxmin就是d
        else cout<<minvol<<" "<<d-maxmin<<endl;//如果没找到，maxmin就是距离d最近的。
    }
    return 0;
}