亚洲国产日本,欧美国产先锋,国内精品视频在线播放

poj 3414解題報(bào)告(廣搜題)

郁悶?zāi)牵瑢?xiě)了七個(gè)小時(shí)，一直在調(diào)試錯(cuò)誤了！fuck it！這個(gè)與別的BFS題的主要不同是要記錄正確順序的路徑,我用path[i][j] = {way，a,b}表示狀態(tài)（i，j）是由狀態(tài)（a，b）經(jīng)過(guò)方式way（一共六種方式）來(lái)得到的；呵呵，郁悶啊！
不過(guò)值得高興地是提交一次成功，呵呵，希望對(duì)大家有所幫助！下面是代碼，很亂，請(qǐng)大家湊合著看吧，現(xiàn)在是沒(méi)心情優(yōu)化了！！

//============================================================================
2

// Name : poj.cpp
3

// Author :
4

// Version :
5

// Copyright : Your copyright notice
6

// Description : BFS
7

//============================================================================
8

#include <iostream>
10

#include <queue>
11

int A, B, C;
12

int j = 1;
13

int result[101][101] = { 0 };
14

using namespace std;
15

struct node {
16

int a;
17

int b;
18

};
19

struct node2 {
20

int pre;
21

int m;
22

int n;
23

} path[101][101];
24

int p[1000];
25

int visited[101][101] = { 0 };
26

int BFS(node x) {
27

queue<node> q;
28

q.push(x);
29

visited[x.a][x.b] = 1;
30

result[x.a][x.b] = 0;
31

path[x.a][x.b].pre = 0;
32

path[0][0].m = path[0][0].n = 0;
33

while (!q.empty()) {
34

node temp = q.front();
35

q.pop();
36

if (temp.a == C)
37

return temp.b;
38

if (temp.b == C) {
39

j = 2;
40

return temp.a;
41

}
42

node y;
43

y.a = A;
44

y.b = temp.b;
45

if (temp.a < A && !visited[A][temp.b]) {
46

q.push(y);
47

visited[A][temp.b] = 1;
48

result[y.a][y.b] = result[temp.a][temp.b] + 1;
49

path[y.a][y.b].pre = 1;
50

path[y.a][y.b].m = temp.a;
51

path[y.a][y.b].n = temp.b;
52

}
53

y.a = temp.a;
54

y.b = B;
55

if (temp.b < B && !visited[y.a][y.b]) {
56

q.push(y);
57

visited[temp.a][B] = 1;
58

result[y.a][y.b] = result[temp.a][temp.b] + 1;
59

path[y.a][y.b].pre = 2;
60

path[y.a][y.b].m = temp.a;
61

path[y.a][y.b].n = temp.b;
62

}
64

y.a = 0;
65

y.b = temp.b;
66

if (temp.a != 0 && !visited[0][temp.b]) {
67

q.push(y);
68

visited[0][temp.b] = 1;
69

result[y.a][y.b] = result[temp.a][temp.b] + 1;
70

path[y.a][y.b].pre = 3;
71

path[y.a][y.b].m = temp.a;
72

path[y.a][y.b].n = temp.b;
73

}
75

y.a = temp.a;
77

y.b = 0;
78

if (temp.b != 0 && !visited[temp.a][0]) {
79

q.push(y);
80

visited[temp.a][0] = 1;
81

result[y.a][y.b] = result[temp.a][temp.b] + 1;
82

path[y.a][y.b].pre = 4;
83

path[y.a][y.b].m = temp.a;
84

path[y.a][y.b].n = temp.b;
85

}
87

y.a = temp.a + temp.b - B;
88

y.b = B;
89

if (temp.a + temp.b > B && !visited[temp.a + temp.b - B][B]) {
90

q.push(y);
91

visited[temp.a + temp.b - B][B] = 1;
92

result[y.a][y.b] = result[temp.a][temp.b] + 1;
93

path[y.a][y.b].pre = 5;
94

path[y.a][y.b].m = temp.a;
95

path[y.a][y.b].n = temp.b;
96

}
98

y.a = 0;
99

y.b = temp.a + temp.b;
100

if (temp.a + temp.b <= B && !visited[0][temp.a + temp.b]) {
101

q.push(y);
102

visited[0][temp.a + temp.b] = 1;
103

result[y.a][y.b] = result[temp.a][temp.b] + 1;
104

path[y.a][y.b].pre = 5;
105

path[y.a][y.b].m = temp.a;
106

path[y.a][y.b].n = temp.b;
107

108

}
109

y.a = A;
110

y.b = temp.a + temp.b - A;
111

if (temp.a + temp.b > A && !visited[A][temp.a + temp.b - A]) {
112

q.push(y);
113

visited[A][temp.a + temp.b - A] = 1;
114

result[y.a][y.b] = result[temp.a][temp.b] + 1;
115

path[y.a][y.b].pre = 6;
116

path[y.a][y.b].m = temp.a;
117

path[y.a][y.b].n = temp.b;
118

}
119

y.a = temp.a + temp.b;
120

y.b = 0;
121

if (temp.a + temp.b <= A && !visited[temp.a + temp.b][0]) {
122

q.push(y);
123

visited[temp.a + temp.b][0] = 1;
124

result[y.a][y.b] = result[temp.a][temp.b] + 1;
125

path[y.a][y.b].pre = 6;
126

path[y.a][y.b].m = temp.a;
127

path[y.a][y.b].n = temp.b;
128

129

}
130

}
131

return -1;
132

}
133

int main() {
134

cin >> A >> B >> C;
135

int i = 1;
136

int ff;
137

node x;
138

x.a = 0;
139

x.b = 0;
140

int m = BFS(x);
141

if (m == -1) {
142

cout << "impossible" << endl;
143

return 0;
144

}
145

if (j == 1) {
146

ff = result[C][m];
147

cout << result[C][m] << endl;
148

int x = C;
149

int y = m;
150

while (path[x][y].pre != 0) {
151

p[i++] = path[x][y].pre;
152

int temp1 = x;
153

int temp2 = y;
154

x = path[temp1][temp2].m;
155

y = path[temp1][temp2].n;
156

}
157

}
158

if (j == 2) {
159

ff = result[m][C];
160

cout << result[m][C] << endl;
161

int x = m;
162

int y = C;
163

while (path[x][y].pre != 0) {
164

p[i++] = path[x][y].pre;
165

int temp1 = x;
166

int temp2 = y;
167

x = path[temp1][temp2].m;
168

y = path[temp1][temp2].n;
169

}
170

}
171

for (int i = ff; i >= 1; i--) {
172

switch (p[i]) {
173

case 1:
174

cout << "FILL(1)" << endl;
175

break;
176

case 2:
177

cout << "FILL(2)" << endl;
178

break;
179

case 3:
180

cout << "DROP(1)" << endl;
181

break;
182

case 4:
183

cout << "DROP(2)" << endl;
184

break;
185

case 5:
186

cout << "POUR(1,2)" << endl;
187

break;
188

case 6:
189

cout << "POUR(2,1)" << endl;
190

break;
191

}
192

193

}
194

return 0;
195

}
196

posted on 2009-03-08 18:40 WORM 閱讀(1676) 評(píng)論(5) 編輯收藏引用

評(píng)論

# re: poj 3414解題報(bào)告(廣搜題)[未登錄](méi) 回復(fù) 更多評(píng)論

垃圾

2009-03-08 18:59 | A

# re: poj 3414解題報(bào)告(廣搜題) 回復(fù) 更多評(píng)論

@A 我承認(rèn)本人是菜鳥(niǎo)，你牛逼你來(lái)搜人家的解題報(bào)告干嘛啊？？

2009-03-08 19:03 | WORM

# re: poj 3414解題報(bào)告(廣搜題)[未登錄](méi) 回復(fù) 更多評(píng)論

我不是搜，訂閱到博客天天是解體報(bào)告。。

2009-03-08 19:55 | A

# re: poj 3414解題報(bào)告(廣搜題) 回復(fù) 更多評(píng)論

已閱刪之

2009-03-08 20:24 | cppexplore

# re: poj 3414解題報(bào)告(廣搜題) 回復(fù) 更多評(píng)論

那我寫(xiě)啥？@A

2009-03-08 20:56 | WORM

刷新評(píng)論列表

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

# re: poj 3414解題報(bào)告(廣搜題)[未登錄](méi) 回復(fù) 更多評(píng)論

# re: poj 3414解題報(bào)告(廣搜題) 回復(fù) 更多評(píng)論

# re: poj 3414解題報(bào)告(廣搜題)[未登錄](méi) 回復(fù) 更多評(píng)論

# re: poj 3414解題報(bào)告(廣搜題) 回復(fù) 更多評(píng)論

# re: poj 3414解題報(bào)告(廣搜題) 回復(fù) 更多評(píng)論

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

worm

poj 3414解題報(bào)告(廣搜題)

評(píng)論

導(dǎo)航

常用鏈接

留言簿(1)

隨筆檔案

文章檔案

相冊(cè)

OJ

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜