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 |
仔细点就好#include<stdio.h> #include<string.h> #include<queue> using namespace std; int A,B,C; struct NODE{ int index; int a,b; }; struct PUTID{ int way; int pre_index; }putid[10005]; int index; bool mark; bool visit[105][105]; bool judge(int a,int b){ if(a == C || b == C) return true; return false; } int Max(int a,int b){ if(a > b) return a; return b; } void OUTPUT(int index,int steps){ if(index == -1) return; OUTPUT(putid[index].pre_index,steps + 1); if(!mark){ printf("%d\n",steps); mark = true; } switch(putid[index].way){ case 1: printf("FILL(1)\n"); break; case 2: printf("FILL(2)\n"); break; case 3: printf("DROP(1)\n"); break; case 4: printf("DROP(2)\n"); break; case 5: printf("POUR(1,2)\n"); break; case 6: printf("POUR(2,1)\n"); break; default: break; } } void CHKoutput(int a,int b,int way){ printf("%d %d WAY:",a,b); switch(way){ case 1: printf("FILL(1)\n"); break; case 2: printf("FILL(2)\n"); break; case 3: printf("DROP(1)\n"); break; case 4: printf("DROP(2)\n"); break; case 5: printf("POUR(1,2)\n"); break; case 6: printf("POUR(2,1)\n"); break; default: break; } } int main() { while(~scanf("%d%d%d",&A,&B,&C)) { if(C > Max(A,B)) continue; struct NODE cur; queue<NODE>q; while(!q.empty()) q.pop(); memset(visit,false,sizeof(visit)); for(int i = 0;i <= 10005; ++i){ putid[i].way = 0; putid[i].pre_index = -1; } mark = false; index = 0; cur.a = 0; cur.b = 0; cur.index = ++index; putid[cur.index].pre_index = -1; putid[cur.index].way = 0; visit[cur.a][cur.b] = true; q.push(cur); while(!q.empty()){ cur = q.front(); q.pop(); //printf("%d %d WAY:%d\n",cur.a,cur.b,putid[cur.index].way); NODE nxt; if(cur.a != A){ nxt.a = A; nxt.b = cur.b; if(!visit[nxt.a][nxt.b]){ nxt.index = ++index; putid[nxt.index].pre_index = cur.index; putid[nxt.index].way = 1; //CHKoutput(nxt.a,nxt.b,putid[nxt.index].way); if(judge(nxt.a,nxt.b)){ OUTPUT(nxt.index,0); break; } visit[nxt.a][nxt.b] = true; q.push(nxt); } } if(cur.b != B){ nxt.a = cur.a; nxt.b = B; if(!visit[nxt.a][nxt.b]){ nxt.index = ++index; putid[nxt.index].pre_index = cur.index; putid[nxt.index].way = 2; //CHKoutput(nxt.a,nxt.b,putid[nxt.index].way); if(judge(nxt.a,nxt.b)){ OUTPUT(nxt.index,0); break; } visit[nxt.a][nxt.b] = true; q.push(nxt); } } if(cur.a != 0){ nxt.a = 0; nxt.b = cur.b; if(!visit[nxt.a][nxt.b]){ nxt.index = ++index; putid[nxt.index].pre_index = cur.index; putid[nxt.index].way = 3; //CHKoutput(nxt.a,nxt.b,putid[nxt.index].way); if(judge(nxt.a,nxt.b)){ OUTPUT(nxt.index,0); break; } visit[nxt.a][nxt.b] = true; q.push(nxt); } } if(cur.b != 0){ nxt.a = cur.a; nxt.b = 0; if(!visit[nxt.a][nxt.b]){ nxt.index = ++index; putid[nxt.index].pre_index = cur.index; putid[nxt.index].way = 4; //CHKoutput(nxt.a,nxt.b,putid[nxt.index].way); if(judge(nxt.a,nxt.b)){ OUTPUT(nxt.index,0); break; } visit[nxt.a][nxt.b] = true; q.push(nxt); } } if(cur.a != 0 && cur.b != B){ if(cur.a <= B - cur.b){ nxt.a = 0; nxt.b = cur.b + cur.a; } else{ nxt.a = cur.a - (B - cur.b); nxt.b = B; } if(!visit[nxt.a][nxt.b]){ nxt.index = ++index; putid[nxt.index].pre_index = cur.index; putid[nxt.index].way = 5; //CHKoutput(nxt.a,nxt.b,putid[nxt.index].way); if(judge(nxt.a,nxt.b)){ OUTPUT(nxt.index,0); break; } visit[nxt.a][nxt.b] = true; q.push(nxt); } } if(cur.a != A && cur.b != 0){ if(cur.b <= A - cur.a){ nxt.a = cur.a + cur.b; nxt.b = 0; } else{ nxt.a = A; nxt.b = cur.b - (A - cur.a); } if(!visit[nxt.a][nxt.b]){ nxt.index = ++index; putid[nxt.index].pre_index = cur.index; putid[nxt.index].way = 6; //CHKoutput(nxt.a,nxt.b,putid[nxt.index].way); if(judge(nxt.a,nxt.b)){ OUTPUT(nxt.index,0); break; } visit[nxt.a][nxt.b] = true; q.push(nxt); } } } if(!mark) printf("impossible\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator