题解: 水杯倒水的问题非常经典,套路也是一样的,bfs找出全部状态。
这道题的关键在于每次都应该进行六次的倒水尝试,细心一点。PS:三维数组表示状态真的非常方便。
代码实现:
/*ID: eashionLANG: C++TASK: milk3*/#include#include #include #include #include #include #define MAX 22using namespace std;struct state{ int a,b,c;};int A,B,C;int save[MAX];queue Q;int show[MAX][MAX][MAX];int main(){ freopen("milk3.in","r",stdin); freopen("milk3.out","w",stdout); while( scanf("%d%d%d",&A,&B,&C) != EOF ){ int pos = 0; memset(save,0,sizeof(save)); memset(show,0,sizeof(show)); show[0][0][C] = 1; state tmp; tmp.a = 0; tmp.b = 0; tmp.c = C; Q.push(tmp); while( !Q.empty() ){ state cur; cur = Q.front(); Q.pop(); if( cur.a == 0 ){ save[pos] = cur.c; pos++; } state nstate; int ta,tb,tc; if( cur.a != 0 ){ ta = cur.a; tb = cur.b; tc = cur.c; if( ta+tb <= B ){ tb += ta; ta = 0; tc = cur.c; } else{ ta = ta+tb-B; tb = B; tc = cur.c; } if( show[ta][tb][tc] != 1 ){ nstate.a = ta; nstate.b = tb; nstate.c = tc; Q.push(nstate); show[ta][tb][tc] = 1; } ta = cur.a; tb = cur.b; tc = cur.c; if( ta+tc <= C ){ tc += ta; ta = 0; tb = cur.b; } else{ ta = ta+tc-C; tc = C; tb = cur.b; } if( show[ta][tb][tc] != 1 ){ nstate.a = ta; nstate.b = tb; nstate.c = tc; Q.push(nstate); show[ta][tb][tc] = 1; } } if( cur.b != 0 ){ ta = cur.a; tb = cur.b; tc = cur.c; if( ta+tb <= A ){ ta += tb; tb = 0; tc = cur.c; } else{ tb = ta+tb-A; ta = A; tc = cur.c; } if( show[ta][tb][tc] != 1 ){ nstate.a = ta; nstate.b = tb; nstate.c = tc; Q.push(nstate); show[ta][tb][tc] = 1; } ta = cur.a; tb = cur.b; tc = cur.c; if( tb+tc <= C ){ tc += tb; tb = 0; ta = cur.a; } else{ tb = tb+tc-C; tc = C; ta = cur.a; } if( show[ta][tb][tc] != 1 ){ nstate.a = ta; nstate.b = tb; nstate.c = tc; Q.push(nstate); show[ta][tb][tc] = 1; } } if( cur.c != 0 ){ ta = cur.a; tb = cur.b; tc = cur.c; if( tc+tb <= B ){ tb += tc; tc = 0; ta = cur.a; } else{ tc = tc+tb-B; tb = B; ta = cur.a; } if( show[ta][tb][tc] != 1 ){ nstate.a = ta; nstate.b = tb; nstate.c = tc; Q.push(nstate); show[ta][tb][tc] = 1; } ta = cur.a; tb = cur.b; tc = cur.c; if( ta+tc <= A ){ ta += tc; tc = 0; tb = cur.b; } else{ tc = ta+tc-A; ta = A; tb = cur.b; } if( show[ta][tb][tc] != 1 ){ nstate.a = ta; nstate.b = tb; nstate.c = tc; Q.push(nstate); show[ta][tb][tc] = 1; } } } sort(save,save+pos); for( int i = 0; i < pos; i++ ){ if( i != pos-1 ){ printf("%d ",save[i]); } else{ printf("%d\n",save[i]); } } } return 0;}