Koios1143的筆記

UVa 571

發表於 分類於

UVa 571

題目

http://domen111.github.io/UVa-Easy-Viewer/?571

倒水問題，給兩個容量分別為 $A, B$ 加侖的桶子，有 $6$ 種操作

  • fill A
  • fill B
  • empty A
  • empty B
  • pour A B
  • pour B A

請問最少要花多少步驟可以組合出 $N$ 加侖的水

想法

因為要問的是最小的步驟，所以可以想到用 BFS 來搜尋解法

每次檢查六種操作是否可以執行，然後枚舉出所有的操作，直到組合出 $N$ 加侖的水

Code

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
//By Koios1143
#include<iostream>
using namespace std;
int a, b, max_a, max_b, cur_a, cur_b, n, ans;
string methods[] = {"fill A", "fill B", "empty A", "empty B", "pour A B", "pour B A"};
/*
methods:
0: fill A
1: fill B
2: empty A
3: empty B
4: pour A B
5: pour B A
*/
/*
0: cur_a
1: cur_b
2: 從哪個點來的
3: 用的方法編號
*/
int res[1000005], que[1005][4];
bool vis[1005][1005];

void BFS(){
	que[0][0] = 0;
	que[0][1] = 0;
	que[0][2] = -1;
	que[0][3] = -1;
	vis[0][0] = true;
	
	for(int i=0, j=1 ; i<j ; i++){
		cur_a = que[i][0];
		cur_b = que[i][1];
		if(cur_a == n || cur_b == n){
			ans = i;
			return;
		}
		
		if(cur_a != max_a && !vis[max_a][cur_b]){
			// fill A
			vis[max_a][cur_b] = true;
			que[j][0] = max_a;
			que[j][1] = cur_b;
			que[j][2] = i;
			que[j][3] = 0;
			j++;
		}
		if(cur_b != max_b && !vis[cur_a][max_b]){
			// fill B
			vis[cur_a][max_b] = true;
			que[j][0] = cur_a;
			que[j][1] = max_b;
			que[j][2] = i;
			que[j][3] = 1;
			j++;
		}
		if(cur_a != 0 && !vis[0][cur_b]){
			// empty A
			vis[0][cur_b] = true;
			que[j][0] = 0;
			que[j][1] = cur_b;
			que[j][2] = i;
			que[j][3] = 2;
			j++;
		}
		if(cur_b != 0 && !vis[cur_a][0]){
			// empty B
			vis[cur_a][0] = true;
			que[j][0] = cur_a;
			que[j][1] = 0;
			que[j][2] = i;
			que[j][3] = 3;
			j++;
		}
		if(max_b-cur_b >= cur_a){
			// pour A B
			if(!vis[0][cur_b+cur_a]){
				vis[0][cur_b+cur_a] = true;
				que[j][0] = 0;
				que[j][1] = cur_b+cur_a;
				que[j][2] = i;
				que[j][3] = 4;
				j++;
			}
		}
		else{
			if(!vis[cur_a-(max_b-cur_b)][max_b]){
				vis[cur_a-(max_b-cur_b)][max_b] = true;
				que[j][0] = cur_a-(max_b-cur_b);
				que[j][1] = max_b;
				que[j][2] = i;
				que[j][3] = 4;
				j++;
			}
		}
		if(max_a-cur_a >= cur_b){
			// pour B A
			if(!vis[cur_a+cur_b][0]){
				vis[cur_a+cur_b][0] = true;
				que[j][0] = cur_a+cur_b;
				que[j][1] = 0;
				que[j][2] = i;
				que[j][3] = 5;
				j++;
			}
		}
		else{
			if(!vis[max_a][cur_b-(max_a-cur_a)]){
				vis[max_a][cur_b-(max_a-cur_a)] = true;
				que[j][0] = max_a;
				que[j][1] = cur_b-(max_a-cur_a);
				que[j][2] = i;
				que[j][3] = 5;
				j++;
			}
		}
	}
}

// 利用遞迴的方式輸出過程
void print_ans(int cur){
	if(que[cur][2] == -1){
		return;
	}
	print_ans(que[cur][2]);
	cout<<methods[que[cur][3]]<<"\n";
}

int main(){
	while(cin>>max_a>>max_b>>n){
		ans=-1;
		for(int i=0 ; i<1005 ; i++){
			for(int j=0 ; j<1005 ; j++){
				vis[i][j] = 0;
			}
		}
		BFS();
		print_ans(ans);
		cout<<"success\n";
	}
	return 0;
}