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<queue> #include<cstring> #include<vector> using namespace std; struct State{ int i, j; vector<int> steps; }; int vis[105][105]; int a, b, c; void print(vector<int> t) { if(!t.empty()) { cout << t.size() << endl; for(int i = 0; i < t.size(); i++) if(t[i] == 1) cout << "FILL(1)\n"; else if(t[i] == 2) cout << "DROP(1)\n"; else if(t[i] == 3) cout << "POUR(1,2)\n"; else if(t[i] == 4) cout << "FILL(2)\n"; else if(t[i] == 5) cout << "DROP(2)\n"; else if(t[i] == 6) cout << "POUR(2,1)\n"; else continue; } else cout << "impossible\n"; } void bfs(State p) { queue<State> Q; memset(vis, 0, sizeof(vis)); Q.push(p); vis[p.i][p.j] = 1; while(!Q.empty()) { State tmp = Q.front(); Q.pop(); if(tmp.i == c || tmp.j == c) { print(tmp.steps); return ; } State np = tmp; np.i = a; np.j = tmp.j; if(!vis[np.i][np.j]) { vis[np.i][np.j] = 1; np.steps.push_back(1); Q.push(np); } np = tmp; np.i = 0; np.j = tmp.j; if(!vis[np.i][np.j]) { vis[np.i][np.j] = 1; np.steps.push_back(2); Q.push(np); } np = tmp; int cha = b - tmp.j; if(np.i >= cha) { np.j = b; np.i = tmp.i - cha; } else { np.j = tmp.j + tmp.i; np.i = 0; } if(!vis[np.i][np.j]) { vis[np.i][np.j] = 1; np.steps.push_back(3); Q.push(np); } np = tmp; np.j = b; np.i = tmp.i; if(!vis[np.i][np.j]) { vis[np.i][np.j] = 1; np.steps.push_back(4); Q.push(np); } np = tmp; np.j = 0; np.i = tmp.i; if(!vis[np.i][np.j]) { vis[np.i][np.j] = 1; np.steps.push_back(5); Q.push(np); } np = tmp; cha = a - tmp.i; if(np.j >= cha) { np.i = a; np.j = tmp.j - cha; } else { np.i = tmp.j + tmp.i; np.j = 0; } if(!vis[np.i][np.j]) { vis[np.i][np.j] = 1; np.steps.push_back(6); Q.push(np); } } cout << "impossible\n" << endl; } int main() { cin >> a >> b >> c; vector<int> q; bfs(State{0, 0, q}); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator