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> using namespace std; int a, b, c; bool ava = false; bool vis[101][101]; struct tree { tree* father; int op; tree(tree* father, int op) : father(father), op(op) {} }; struct node { int a; int b; tree* t; }; queue<node> q; tree* bfs() { while(!q.empty()) { tree *father = q.front().t; int anow = q.front().a; int bnow = q.front().b; q.pop(); node n; for(int i = 0; i < 6; i++) { int anext = anow; int bnext = bnow; switch(i) { case 0: { if(anow < a) { anext = a; } break; } case 1: { if(anow) { anext = 0; } break; } case 2: { if(anow) { if(anow + bnow <= b) { bnext = anow + bnow; anext = 0; } else { anext = anow + bnow - b; bnext = b; } } break; } case 3: { if(bnow < b) { bnext = b; } break; } case 4: { if(bnow) { bnext = 0; } break; } case 5: { if(bnow) { if(anow + bnow <= a) { anext = anow + bnow; bnext = 0; } else { bnext = anow + bnow - a; anext = a; } } break; } } if(!vis[anext][bnext]) { vis[anext][bnext] = true; node n; n.a = anext; n.b = bnext; n.t = new tree(father, i); if(anext == c || bnext == c) { ava = true; return n.t; } q.push(n); } } } return NULL; } string findd(int n) { switch(n) { case 0: return "FILL(1)"; case 1: return "DROP(1)"; case 2: return "POUR(1,2)"; case 3: return "FILL(2)"; case 4: return "DROP(2)"; case 5: return "POUR(2,1)"; } } void outPut(tree *t, int n) { if(t->father == NULL) { cout << n << endl; cout << findd(t->op) << endl; return; } outPut(t->father, n + 1); cout << findd(t->op) << endl; return; } int main() { ios::sync_with_stdio(false); cin.tie(0); memset(vis, false, sizeof(vis)); vis[0][0] = true; cin >> a >> b >> c; if(c == a) { cout << 1 << endl; cout << "FILL(1)" << endl; return 0; } else if(c == b) { cout << 1 << endl; cout << "FILL(2)" << endl; return 0; } while(!q.empty()) { q.pop(); } node n; n.a = a; n.b = 0; n.t = new tree(NULL, 0); q.push(n); n.b = b; n.a = 0; n.t = new tree(NULL, 3); q.push(n); vis[0][b] = true; vis[a][0] = true; tree* t = bfs(); if(!ava) { cout << "impossible"; } else { outPut(t, 1); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator