倒水问题

发表于 | 分类于 | | 阅读次数:

设有3个没有刻度的杯子的容量分别是a，b，c，最初只有第3个杯子装满了c升水，其他两个杯子为空。最少需要倒多少升水才能让某一个杯子中的水有d升。如果无法做到恰好有d升，就让某一个杯子里的水是d’升，其中d’< d，并且尽量接近d。

解法

解法和八数码问题一样，关键在于建立图模型，进行状态转移，把状态想象成图中的结点。
fill.png
问题形式有总倒水量最少和总步数最少。如果是总倒水量最少，可以用优先队列priority_queue来维护每个状态当前的总倒水量；如果是总步数最少，就可以用队列来维护状态，采用BFS进行搜索。

总倒水量最少

题目链接Uva10603-Fill

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
 *
 * Author : Aincrad
 *
 * Date : Thu 27 Dec 11:54:46 CST 2018
 *
 */

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200 + 7;
int T;
struct Node{
    int v[3];
    int vol;
    bool operator < (const Node& nd) const {
        return vol > nd.vol;
    }
};
int ans[maxn];
bool vis[maxn][maxn];
int cap[3];

void update_ans(Node nd){
    for(int i = 0; i < 3; i++){
        int d = nd.v[i];
        if(ans[d] < 0 || nd.vol < ans[d]) ans[d] = nd.vol;
    }
}

void solve(int a, int b, int c, int d){
    priority_queue<Node> q;
    Node FirstItem;
    FirstItem.v[0] = 0, FirstItem.v[1] = 0, FirstItem.v[2] = c;
    FirstItem.vol = 0;
    q.push(FirstItem);
    vis[0][0] = 1;
    while(!q.empty()){
        Node nd = q.top();
        q.pop();
        update_ans(nd);
        if(ans[d] >= 0) break;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(i == j) continue;
                if(nd.v[i] == 0 || nd.v[j] == cap[j]) continue;
                int amount = min(cap[j], nd.v[i] + nd.v[j]) - nd.v[j];
                Node NewItem;
                memcpy(&NewItem, &nd, sizeof(NewItem));
                NewItem.v[i] -= amount;
                NewItem.v[j] += amount;
                NewItem.vol += amount;
                if(!vis[NewItem.v[0]][NewItem.v[1]]){
                    q.push(NewItem);
                    vis[NewItem.v[0]][NewItem.v[1]] = 1;
                }
            }
        }
    }
    for(int i = d; i >= 0; i--){
        if(ans[i] >= 0){
            cout << ans[i] << " " << i << endl;
            break;
        }
    }
}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    cin >> T;
    while(T--){
        memset(vis, 0, sizeof(vis));
        memset(ans, -1, sizeof(ans));
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cap[0] = a, cap[1] = b, cap[2] = c;
        solve(a, b, c, d);
    }
    return 0;
}

总步数最少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*
 *
 * Author : Aincrad
 *
 * Date : Mon 31 Dec 09:44:46 CST 2018
 *
 */

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200 + 7;
struct Node{
    int v[3];
    int dis;
};
int cap[3];
bool vis[maxn][maxn];
int ans[maxn];

void update_ans(Node& u){
    for(int i = 0; i < 3; i++){
        int d = u.v[i];
        if(ans[d] < 0 || u.dis < ans[d]) ans[d] = u.dis;
    }
}

void solve(int a, int b, int c, int d){
    queue<Node> que;
    Node FirstItem;
    FirstItem.v[0] = 0, FirstItem.v[1] = 0, FirstItem.v[2] = c;
    FirstItem.dis = 0;
    que.push(FirstItem);
    vis[0][0] = 1;

    while(!que.empty()){
        Node nd = que.front();
        que.pop();
        update_ans(nd);
        if(ans[d] >= 0) break;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(i == j) continue;
                if(nd.v[i] == 0 || nd.v[j] == cap[j]) continue;
                int amount = min(cap[j], nd.v[i] + nd.v[j]) - nd.v[j];
                Node NewItem;
                memcpy(NewItem.v, nd.v, sizeof(NewItem.v));
                NewItem.v[i] -= amount;
                NewItem.v[j] += amount;
                NewItem.dis = nd.dis + 1;
                if(!vis[NewItem.v[0]][NewItem.v[1]]){
                    que.push(NewItem);
                    vis[NewItem.v[0]][NewItem.v[1]] = 1;
                }
            }
        }
    }

    for(int i = d; i >= 0; i--){
        if(ans[i] >= 0){
            cout << ans[i] << " " << i << endl;
            break;
        }
    }
}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif

    memset(vis, 0, sizeof(vis));
    memset(ans, -1, sizeof(ans));
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cap[0] = a, cap[1] = b, cap[2] = c;
    solve(a, b, c, d);

    return 0;
}