| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
就是bfs多了个回溯#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int >P;
queue<P> que;
vector<P> path;
const char* oprate[]={ "FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)" };
int used[1000][1000] = { 0 };
int a, b, c;
int i = -1;
void print(int p,int s) {
if (p == 0) {
cout << s << endl;
return;
}
print(path[p].second,s+1);
cout << oprate[path[p].first] << endl;
}
void bfs() {
P p(0, 0);
que.push(p);
path.push_back(P(0, 0));
bool flag = false;
while (!que.empty()) {
P cur = que.front();
que.pop();
i++;
if (cur.first == c || cur.second == c) {
flag = true;
break;
}
if (!used[cur.first][cur.second]) {
used[cur.first][cur.second] = 1;
que.push(P(a, cur.second));
path.push_back(P(0, i));
que.push(P(cur.first, b));
path.push_back(P(1, i));
que.push(P(0, cur.second));
path.push_back(P(2, i));
que.push(P(cur.first, 0));
path.push_back(P(3, i));
que.push(P(max(cur.first - b + cur.second, 0), min(b, cur.second + cur.first)));
path.push_back(P(4, i));
que.push(P(min(a, cur.first + cur.second), max(cur.second - a + cur.first, 0)));
path.push_back(P(5, i));
}
}
if (flag)
print(i,0);
else
cout << "impossible\n";
}
int main() {
cin >> a >> b >> c;
bfs();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator