[POJ-3414]Pots

xiaoxiao2021-02-28  49

#include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<cmath> #include<ctype.h> #include<algorithm> #include<queue> #include<vector> using namespace std; const int maxn = 100 + 12; struct Node { int a, b; int t; int s, f; Node(int aa, int bb, int tt, int ss, int ff): a(aa), b(bb), t(tt), s(ss), f(ff) { } }; struct Order { string st; int s; int f; Order(string sst, int ss, int ff): st(sst), s(ss), f(ff) { } }; bool vis[maxn][maxn]; vector<Order> V; void Print( int a ) { if( V[a].f != 0 ) { Print(V[a].f); } cout << V[a].st << endl; } int main() { int A, B, C; while( cin >> A >> B >> C ) { memset( vis, 0, sizeof(vis) ); queue<Node> Q; V.clear(); Q.push( Node(0,0,0,0,-1) ); V.push_back( Order("NULL",0,-1) ); vis[0][0] = 1; int mark = -1; int cnt = 0; while( !Q.empty() ) { Node q = Q.front(); if( q.a==C || q.b==C ) { cout << q.t << endl; mark = q.s; break; } for(int i=0; i<6; i++) { int ta, tb; if( i==0 ) { ta = A; tb = q.b; if( vis[ta][tb] ) { continue; } ++cnt; vis[ta][tb] = 1; Q.push( Node(ta,tb,q.t+1,cnt,q.s) ); V.push_back( Order("FILL(1)",cnt,q.s) ); } if( i==1 ) { ta = q.a; tb = B; if( vis[ta][tb] ) { continue; } ++cnt; vis[ta][tb] = 1; Q.push( Node(ta,tb,q.t+1,cnt,q.s) ); V.push_back( Order("FILL(2)",cnt,q.s) ); } if( i==2 ) { ta = 0; tb = q.b; if( vis[ta][tb] ) { continue; } ++cnt; vis[ta][tb] = 1; Q.push( Node(ta,tb,q.t+1,cnt,q.s) ); V.push_back( Order("DROP(1)",cnt,q.s) ); } if( i==3 ) { ta = q.a; tb = 0; if( vis[ta][tb] ) { continue; } ++cnt; vis[ta][tb] = 1; Q.push( Node(ta,tb,q.t+1,cnt,q.s) ); V.push_back( Order("DROP(2)",cnt,q.s) ); } if( i==4 ) { if( q.a >= B-q.b ) { ta = q.a-(B-q.b); tb=B; } else { tb = q.b+q.a; ta=0; } if( vis[ta][tb] ) { continue; } ++cnt; vis[ta][tb] = 1; Q.push( Node(ta,tb,q.t+1,cnt,q.s) ); V.push_back( Order("POUR(1,2)",cnt,q.s) ); } if( i==5 ) { if( q.b >= A-q.a ) { tb = q.b-(A-q.a); ta=A; } else { ta = q.a+q.b; tb=0; } if( vis[ta][tb] ) { continue; } ++cnt; vis[ta][tb] = 1; Q.push( Node(ta,tb,q.t+1,cnt,q.s) ); V.push_back( Order("POUR(2,1)",cnt,q.s) ); } } Q.pop(); } if( mark == -1 ) { cout << "impossible" << endl; } else { Print( mark ); } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-85730.html

最新回复(0)