BFS+剪枝.所謂的剪枝就是如果A為空的時候不能進行"empty A"的操作等.
PS:也可利用A和B的互質性解決,在此用搜索主要是想多練習一下搜索的代碼.
Code
1
#include <iostream>
2#include <string>
3#include <queue>
4using namespace std;
5
6const string description[7] =
7
{
8
"",
9 "fill A",
10 "fill B",
11 "empty A",
12 "empty B",
13 "pour A B",
14 "pour B A"
15
};
16
17enum Action
18{
19 NONE = 0,
20 FILL_A,
21 FILL_B,
22 EMPTY_A,
23 EMPTY_B,
24 POUR_A_B,
25 POUR_B_A
26};
27
28struct State
29{
30 int A;
31 int B;
32 State * LastState;
33 Action LastAction;
34
35 bool operator==(const State & state) const
36
{
37 return A == state.A && B == state.B;
38
}
39};
40
41bool IsVisit(State * state, vector<State *> & states)
42{
43 vector<State *>::iterator ite = states.begin();
44 vector<State *>::iterator end = states.end();
45 while(ite != end)
46 {
47 if(*state == *(*ite))
48 return true;
49 ++ite;
50 }
51 return false;
52}
53
54bool IsSuccess(const State * state, int goal)
55{
56 return state->B == goal;
57}
58
59void StoreState(State * last_state, State * state, vector<State *> & visited, queue<State *> & q, Action action)
60{
61 if(!IsVisit(state, visited))
62 {
63 state->LastState = last_state;
64 state->LastAction = action;
65 q.push(state);
66 visited.push_back(state);
67 }
68}
69
70int _tmain(int argc, _TCHAR* argv[])
71{
72 int A, B, goal;
73 vector<State *> visited;
74 queue<State *> q;
75 while(cin >> A >> B >> goal)
76 {
77 State * empty_state = new State();
78 State * next_state;
79 empty_state->A = empty_state->B = 0;
80 empty_state->LastAction = NONE;
81 visited.push_back(empty_state);
82 q.push(empty_state);
83
84 while(!q.empty())
85 {
86 State * current_state = q.front();
87 q.pop();
88
89 // Fill A
90 if(current_state->A < A)
91 {
92 next_state = new State();
93 next_state->A = A;
94 next_state->B = current_state->B;
95 StoreState(current_state, next_state, visited, q, FILL_A);
96 if(IsSuccess(next_state, goal))
97 break;
98 }
99 // Fill B
100 if(current_state->B < B)
101 {
102 next_state = new State();
103 next_state->A = current_state->A;
104 next_state->B = B;
105 StoreState(current_state, next_state, visited, q, FILL_B);
106 if(IsSuccess(next_state, goal))
107 break;
108 }
109 // Empty A
110 if(current_state->A != 0)
111 {
112 next_state = new State();
113 next_state->A = 0;
114 next_state->B = current_state->B;
115 StoreState(current_state, next_state, visited, q, EMPTY_A);
116 if(IsSuccess(next_state, goal))
117 break;
118 }
119 // Empty B
120 if(current_state->B != 0)
121 {
122 next_state = new State();
123 next_state->A = current_state->A;
124 next_state->B = 0;
125 StoreState(current_state, next_state, visited, q, EMPTY_B);
126 if(IsSuccess(next_state, goal))
127 break;
128 }
129 // Pour A B
130 if(current_state->A != 0 && current_state->B != B)
131 {
132 next_state = new State();
133 int diff = B - current_state->B;
134 int poured = min(current_state->A, diff);
135 next_state->B = current_state->B + poured;
136 next_state->A = current_state->A - poured;
137 StoreState(current_state, next_state, visited, q, POUR_A_B);
138 if(IsSuccess(next_state, goal))
139 break;
140 }
141 // Pour B A
142 if(current_state->B != 0 && current_state->A != A)
143 {
144 next_state = new State();
145 int diff = A - current_state->A;
146 int poured = min(current_state->B, diff);
147 next_state->A = current_state->A + poured;
148 next_state->B = current_state->B - poured;
149 StoreState(current_state, next_state, visited, q, POUR_B_A);
150 if(IsSuccess(next_state, goal))
151 break;
152 }
153 }
154
155 vector<Action> action_list;
156 State * temp_state = next_state;
157 while(temp_state->LastAction != NONE)
158 {
159 action_list.push_back(temp_state->LastAction);
160 temp_state = temp_state->LastState;
161 }
162
163 vector<Action>::reverse_iterator r_ite = action_list.rbegin();
164 vector<Action>::reverse_iterator r_end = action_list.rend();
165 while(r_ite != r_end)
166 {
167 cout << description[(int)(*r_ite)] << endl;
168 ++r_ite;
169 }
170 cout << "success" << endl;
171
172 delete empty_state, next_state;
173 visited.clear();
174 while(!q.empty())
175 q.pop();
176 }
177
178 return 0;
179}
180
181posted on 2009-03-24 20:49
肖羽思 閱讀(698)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ