倒水问题 + bfs模拟

发表于 | 更新于 | 分类于 ，

HDU1495 非常可乐

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出”NO”。

Input

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以”0 0 0”结束。

Output

如果能平分的话请输出最少要倒的次数，否则输出”NO”。

Sample Input

1
2
3
7 4 3
4 1 3
0 0 0

Sample Output

1
2
NO
3

思路，根据题意进行模拟，什么情况下可以倒 (6种情况) 

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
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int s, n, m, ans;
const int N = 101;
bool v[N][N][N];			 //判重	 
struct node{
	int x, y, z, stp;
	node(int x, int y, int z, int stp) : x(x), y(y), z(z), stp(stp) {	}		// 3 + 1个状态	 
};
bool bfs()
{
	queue<node> q;
	q.push({s, 0, 0, 0});
	v[s][0][0] = 1;
	while(!q.empty())
	{
		int sum;
		node t = q.front();
		q.pop();
		if((t.x == t.y && t.x == s >> 1) || (t.x == t.z && t.x == s >> 1) || (t.y == t.z && t.y == s >> 1))		//平分总量
		{
			ans = t.stp;				//记录答案，返回成功 
			return true;
		}
		for(int i = 0; i < 6; i ++ )		//6种情况 A 3 2  ( 3！) 
			switch(i)	
			{
				case 0:			x -> y 
					if(t.x == 0 || t.y == n)	//x瓶没有， y瓶满，不能倒 
						break;
					sum = t.x + t.y;		//类似于pots问题，先记录总量 
					if(sum >= n)				//倒完还剩一点(可能刚好) ，目标壶会倒满 
					{							 
						if(v[sum - n][n][t.z])		break;
						v[sum - n][n][t.z] = 1;
						q.push({sum - n, n, t.z, t.stp + 1});
					}
					else				//起始盆倒空，所有倒入目标盘 
					{
						if(v[0][sum][t.z])		break;
						v[0][sum][t.z] = 1;
						q.push({0, sum, t.z, t.stp + 1});
					}
					break;
				case 1:
					if(t.x == 0 || t.z == m)
						break;
					sum = t.x + t.z;
					if(sum >= m)
					{
						if(v[sum - m][t.y][m])		break;
						v[sum - m][t.y][m] = 1;
						q.push({sum - m, t.y, m, t.stp + 1});
					}
					else
					{
						if(v[0][t.y][sum])		break;
						v[0][t.y][sum] = 1;
						q.push({0, t.y, sum, t.stp + 1});
					}
					break;
				case 2:
					if(t.y == 0 || t.z == m)
						break;
					sum = t.y + t.z;
					if(sum >= m)
					{
						if(v[t.x][sum - m][m])		break;
						v[t.x][sum - m][m] = 1;
						q.push({t.x ,sum - m, m, t.stp + 1});
					}
					else
					{
						if(v[t.x][0][sum])		break;
						v[t.x][0][sum] = 1;
						q.push({t.x, 0, sum, t.stp + 1});
					}
				case 3:
					if(t.y == n || t.z == 0)
						break;
					sum = t.y + t.z;
					if(sum >= n)
					{
						if(v[t.x][n][sum - n])	break;
						v[t.x][n][sum - n] = 1;
						q.push({t.x , n, sum - n, t.stp + 1});
					}
					else
					{
					    if(v[t.x][sum][0])		break;
						v[t.x][sum][0] = 1;
						q.push({t.x, sum, 0, t.stp + 1});
					}
					break;
				case 4:
					if(t.y == 0 || t.x == s)			//向最大壶倒，不可能溢出和留下水 ，全部倒入，自身变 0 
						break;
					sum = t.y + t.x;
					if(v[sum][0][t.z])		break;
					v[sum][0][t.z] = 1;
					q.push({sum, 0, t.z, t.stp + 1});
				case 5:
					if(t.z == 0 || t.x == s)
						break;
					sum = t.z + t.x;
					if(v[sum][t.y][0])		break;
					v[sum][t.y][0] = 1;
					q.push({sum, t.y, 0, t.stp + 1});
			}
	}
	return false; 
}
int main()
{
	while(scanf("%d %d %d", &s, &n, &m) == 3 && s)
	{
		memset(v, 0, sizeof(v));
		if(s & 1)	cout << "NO\n";			//奇数水量无法平分 
		else
			if(bfs())	cout << ans << endl;
			else cout << "NO\n"; 
	}
	return 0;
}

Pots POJ - 3414

模拟bfs（涉及最小步数问题)

你有两个罐子，分别有A和B升的体积。可以执行以下操作：

FILL（i）把水壶i倒满(1≤i≤2）;
DROP（i）把水壶i倒空;
POUR（i，j）从锅i倒入锅j;在此操作之后，罐j已满（并且罐i中可能存在一些水），或罐i是空的（并且其所有水已被移动到罐j）。
编写一个程序来找到这些操作的最短可能序列，这些操作将在其中一个罐中产生完全C升的水。

输入

一行上是数字A，B和C.这些都是1到100之间的整数，并且C≤max（A，B）。

输出

输出的第一行必须包含操作序列K的长度。以下K行必须各自描述一个操作。如果有几个最小长度的序列，则输出其中任何一个。如果无法实现所需的结果，则文件的第一行和唯一行必须包含“impossible”一词。

样本输入

1
3 5 4

样本输出

1
2
3
4
5
6
7
6
FILL（2）
POUR（2,1）
DROP（1）
POUR（2,1）
FILL（2）
POUR（2,1）

思路

6种情况，进行判重，由于每个节点由一个前驱节点转移过来，所以用node pre[N][N]保存前驱节点

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
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
int a, b, c;
const int N = 115;
bool v[N][N];
vector<int> path; 			//倒序输出节点 
struct node{
	int x, y, stp;
	node() {	}
	node(int x, int y, int stp) : x(x), y(y), stp(stp) {	}
};
node pre[N][N], ans;		//保存前驱点 
bool bfs()
{
	int sum;
	queue<node> q;
	q.push({0, 0, 0});
	v[a][b] = 1;
	while(!q.empty())
	{
		node t = q.front();
		q.pop();
		if(t.x == c || t.y == c)
		{
			ans = t;
			return true;
		}
		for(int i = 0; i < 6; i ++ )
		{
			node ne = t;
			switch(i)
			{
				case 0:			//把x瓶倒满 
					ne.x = a;
					break;	
				case 1:
					ne.y = b;	//把y瓶倒满 
					break;
				case 2:
					ne.x = 0;		//把x瓶倒空 
					break;
				case 3:
					ne.y = 0;		//把y瓶倒空 
					break;
				case 4:
					sum = ne.x + ne.y;		//总水量 
					if(sum >= b)		//倒入y中，多余的部分倒入x中 
						ne.y = b, ne.x = sum - b;	
					else	ne.x = 0, ne.y = sum;
					break;
				case 5:	
					sum = ne.x + ne.y;
					if(sum >= a)	//倒入x中，多余的部分导入y中 
						ne.x = a, ne.y = sum - a;
					else	ne.x = sum, ne.y = 0;
					break;
			}
			
			if(!v[ne.x][ne.y])			//判重，由于每个点只访问一次 
			{
				pre[ne.x][ne.y] = {t.x, t.y, i};
				q.push({ne.x, ne.y, t.stp + 1});
			}
			v[ne.x][ne.y] = 1;
 		}
	}
	return false;
}

void print()
{
	cout << ans.stp << endl;
	while(!(ans.x == 0 && ans.y == 0))				//从终点开始往前找前驱节点直到起点 
	{
		int i = pre[ans.x][ans.y].stp;
		path.push_back(i);
		ans = pre[ans.x][ans.y];
	}
	reverse(path.begin(), path.end());			//反向找的，逆序回来 
	for(vector<int> :: iterator i = path.begin(); i < path.end(); i ++)
		switch(*i)
		{
			case 0:			//6种情况对应输出 
				cout << "FILL(1)\n";
				break;
			case 1:
				cout << "FILL(2)\n";
				break;
			case 2:
				cout << "DROP(1)\n";
				break;
			case 3:
				cout << "DROP(2)\n";
				break;
			case 4:
				cout << "POUR(1,2)\n";
				break;
			case 5:
				cout << "POUR(2,1)\n";
				break;
		}
}

int main()
{
	cin >> a >> b >> c;
	if(bfs())	print();
	else cout << "impossible\n" << endl;
	return 0;
}
0%