给出两个壶的容量A和B, 一个目标水量C，对A、B可以有３种操作，求最少经过几步操作能够在某个壶中得到目标水量C。输入A、B和C，输入最少操作数和操作过程。
这道题和上一道搜索题目(hdu1495)的建模是几乎一样,要说不一样的,也没啥不一样的了 .
需要记录最短路径
那道题是有三个杯子可以相互作为中间态，一种有六种状态进行到水,这个虽然只有2个杯子，一个理论的状态量，但限制了给定3种倒水策略
所以还是6中方式(太麻烦了，bfs都这么长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
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=105;
int vis[maxn][maxn];
int n,m,enen;
struct node{
int x,y;
int step;
char path[maxn];
int cnt;
};
string path[] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
void work(int step,char pa[],int cnt){
printf("%d\n",step);
for(int i=0;i<cnt;++i)
cout<<path[pa[i]]<<endl;
}
void bfs(){
queue<node>q;
memset(vis,0,sizeof(vis));
node p,tmp;
p.x=0,p.y=0,p.step=0,p.cnt=0;
vis[0][0]=1;
q.push(p);
while(!q.empty()){
p=q.front();
q.pop();
// cout<<p.x<<' '<<p.y<<endl;
if(p.x==enen||p.y==enen){
work(p.step,p.path,p.cnt);
return ;
}
tmp=p;
tmp.step++;
tmp.cnt++;
//FILL(n)
if(n>p.x){
tmp.x=n;
tmp.y=p.y;
if(!vis[tmp.x][tmp.y]){
tmp.path[p.cnt]=0;
q.push(tmp);
vis[tmp.x][tmp.y]=1;
}
}
//Fill(m)
if(m>p.y){
tmp.x=p.x;
tmp.y=m;
if(!vis[tmp.x][tmp.y]){
tmp.path[p.cnt]=1;
q.push(tmp);
vis[tmp.x][tmp.y]=1;
}
}
//DROP(n)
if(p.x){
tmp.x=0,tmp.y=p.y;
if(!vis[tmp.x][tmp.y]){
tmp.path[p.cnt]=2;
q.push(tmp);
vis[tmp.x][tmp.y]=1;
}
}
//DROP(m)
if(p.y){
tmp.x=p.x;
tmp.y=0;
if(!vis[tmp.x][tmp.y])
{
tmp.path[p.cnt]=3;
q.push(tmp);
vis[tmp.x][tmp.y]=1;
}
}
//POUR(n,m)
if(p.x&&(p.y<m)){
if(p.x>(m-p.y)){
tmp.x=p.x-(m-p.y);
tmp.y=m;
}
else{
tmp.x=0;
tmp.y=p.y+p.x;
}
if(!vis[tmp.x][tmp.y]){
tmp.path[p.cnt]=4;
q.push(tmp);
vis[tmp.x][tmp.y]=1;
}
}
//POUR(m,n)
if(p.y&&(p.x<n)){
if(p.y>(n-p.x)){
tmp.x=n;
tmp.y=p.y-(n-p.x);
}
else{
tmp.x=p.x+p.y;
tmp.y=0;
}
if(!vis[tmp.x][tmp.y])
{
tmp.path[p.cnt]=5;
q.push(tmp);
vis[tmp.x][tmp.y]=1;
}
}
}
printf("impossible\n");
}
int main(){
while(scanf("%d%d%d",&n,&m,&enen)!=EOF){
bfs();
}
return 0;
}
poj3414Pots
-------------本文结束感谢您的阅读-------------