本文主要是介绍pku 3414 pots，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
3414 Pots 经典倒水问题，要求最短，宽搜，ax + by = c 有
解条件
c = 0 (mod gcd(a,b))
#include < iostream > #define MAX_LEN 10001 using namespace std; int a,b,c;
bool black[ 101 ][ 101 ] = ... {false} ; struct Node ... {
int a,b; int level; int prev; char s;
} ;Node que[MAX_LEN]; int top = 0 ,end = 0 ;inline void pour( int & c, int & d, int vol) ... { if (c+d > vol)
...{ c -= vol-d; d = vol;
} else ...{ d += c; c =0; }} bool expand() ... { //fill Node tmp = que[top]; if (tmp.a !=a && black[a][tmp.b] ==false) ...{ tmp.a = a; ++tmp.level; tmp.s = 'f'; tmp.prev = top; black[tmp.a][tmp.b] = true; que[end++] = tmp; } tmp = que[top]; if (tmp.b != b && black[tmp.a][b] ==false) ...{ tmp.b = b; ++tmp.level; tmp.s = 'f'; tmp.prev = top; black[tmp.a][tmp.b] = true; que[end++] = tmp; } //drop tmp = que[top]; if (tmp.a != 0 && black[0][tmp.b] ==false) ...{ tmp.a = 0; ++tmp.level; tmp.s = 'd'; tmp.prev = top; black[0][tmp.b] = true; que[end++] = tmp; } tmp = que[top]; if (tmp.b != 0 && black[tmp.a][0]==false) ...{ tmp.b = 0; ++tmp.level; tmp.s = 'd'; tmp.prev = top; black[tmp.a][0] = true; que[end++] = tmp; } // pour 1 -> 2 tmp = que[top]; if (tmp.a != 0 && tmp.b!=b) ...{ pour(tmp.a, tmp.b,b); if (!black[tmp.a][tmp.b]) ...{ ++tmp.level; tmp.s = 'p'; tmp.prev = top; black[tmp.a][tmp.b] = true; que[end++] = tmp; if (tmp.a == c || tmp.b == c) return false; } } // pour 2 -> 1 tmp = que[top]; if (tmp.b != 0 && tmp.a!=a) ...{ pour(tmp.b, tmp.a,a); if (!black[tmp.a][tmp.b]) ...{ ++tmp.level; tmp.prev = top; tmp.s = 'p'; black[tmp.a][tmp.b] = true; que[end++] = tmp; if (tmp.a == c || tmp.b == c) return false; } } ++top; return true;} void print( int idx) ... { if (idx == 0) return; int ti = que[idx].prev; print(ti); if (que[idx].s == 'f') ...{ if (que[ti].a !=a && que[idx].a ==a) cout<<"FILL(1)"<<endl; else cout<<"FILL(2)"<<endl; } else if (que[idx].s == 'd') ...{ if (que[ti].a !=0 && que[idx].a ==0) cout<<"DROP(1)"<<endl; else cout<<"DROP(2)"<<endl; } else ...{ if (que[ti].a > que[idx].a) ...{ cout<<"POUR(1,2)"<<endl; } else ...{ cout<<"POUR(2,1)"<<endl; } }} bool search() ... { top = 0; que[0].a = que[0].b = 0; que[0].level = 0; black[0][0]= true; end = 1; while (top!= end && expand()); return top!=end;} int main() ... { cin>>a>>b>>c; if (a == c) ...{ cout<<"1 FILL(1)"<<endl; return 0; } if (b == c) ...{ cout<<"1 FILL(2)"<<endl; return 0; } if (search()) ...{ cout<<que[end-1].level<<endl; print(end-1); } else ...{ cout<<"impossible"<<endl; } return 0;}
这篇关于pku 3414 pots的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
