题目连接:
题目大意:给你A,B两个杯子和一同水,问你能用两个杯子倒出C的水吗,
解题思路,这个题和这个题很相似,其实差不多,但是这个题比较麻烦一些,,标记各种情况
#include#include #include #include #include using namespace std;int a,b,c;const int maxn = 100+5;int r,l,v[maxn][maxn];pair q[maxn*maxn];int x[maxn*maxn],p[maxn*maxn],op[maxn*maxn],d[maxn*maxn];void init(){ memset(x,0,sizeof(x)); memset(p,0,sizeof(p)); memset(op,0,sizeof(op)); memset(d,0,sizeof(d));}void check(int i,int j,int o,int k){ //A中的水是i,B中的水是j,操作方法是0,操作的杯子是k if(v[i][j]) return ; v[i][j]=1; //标记当前状态 p[r]=l; //标记当前位置 op[r]=o,x[r]=k,d[r]=d[l]+1; //op记录操作方法,x记录操作的杯子,d记录操作的次数 q[r++]=make_pair(i,j); //把新状态放在队列里面 }int bfs(){ int ca,cb=l=r=0; q[r++]=make_pair(0,0); memset(v,0,sizeof(v)); v[0][0]=1; while(r>l){ ca = q[l].first; cb = q[l].second; if(ca == c || cb == c) return l; check(a,cb,1,1); //装满A中的水 check(ca,b,1,2); //装满B中的水 check(0,cb,2,1); //倒掉A中的水 check(ca,0,2,2); //倒掉B中的水 if(ca > b - cb) check(ca - b + cb , b,3,1); //把A中的水倒满B else check(0,ca+cb,3,1); if(cb > a - ca ) check(a,cb-a+ca,3,2); //把B中的水倒满A else check(ca+cb,0,3,2); ++l; //队列加一 } return 0;}void print(int k){ if(p[k]>0) print(p[k]); if(op[k] == 1) printf("FILL(%d)\n", x[k]); if(op[k] == 2) printf("DROP(%d)\n", x[k]); if(op[k] == 3) printf("POUR(%d,%d)\n", x[k], 3 - x[k]);}int main(){ while(~scanf("%d%d%d",&a,&b,&c)){ init(); int ans=0; if(ans=bfs()){ printf("%d\n",d[ans]); print(ans); }else printf("impossible\n"); } return 0;}