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