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 <algorithm> #include <iostream> #include <sstream> #include <fstream> #include <cstring> #include <cstdlib> #include <cstring> #include <vector> #include <queue> #include <cstdio> #include <cmath> #include <string> #include <stack> #include <map> #include <new> #include <set> #define inf 0x3f3f3f3f #define M 1006 #define stop system("pause") using namespace std; int vis[M][M]; struct node { int aleft; int bleft; int step; }; struct pre{ int num; int operat; } next[M]; void prin(int x){ x=next[x].num; if(x==-1) return; else prin (x); if(next[x].operat==1) puts("FILL(1)"); else if(next[x].operat==2) puts("FILL(2)"); else if(next[x].operat==3) puts("DROP(1)"); else if(next[x].operat==4) puts("DROP(2)"); else if(next[x].operat==5) puts("POUR(1,2)"); else if(next[x].operat==6) puts("POUR(2,1)"); } void bfs(int A,int B,int C){ queue<node> q; node t,p,temp; int f=0; t.aleft=0; t.bleft=0; t.step=0; int head=0,tail=1; next[0].num=-1; memset(vis,0,sizeof(vis)); vis[t.aleft][t.bleft]=1; q.push(t); while(!q.empty()){ p=q.front(); q.pop(); if(p.aleft==C || p.bleft==C ) { printf("%d\n",p.step); int u=head; prin(head); if(next[u].operat==1) puts("FILL(1)"); else if(next[u].operat==2) puts("FILL(2)"); else if(next[u].operat==3) puts("DROP(1)"); else if(next[u].operat==4) puts("DROP(2)"); else if(next[u].operat==5) puts("POUR(1,2)"); else if(next[u].operat==6) puts("POUR(2,1)"); f=1; return ; } for(int i=1;i<=7;i++){ if(i==1){ //fill a if(p.aleft!=A&&!vis[A][p.bleft]){ vis[A][p.bleft]=1; temp.aleft=A; temp.bleft=p.bleft; temp.step=p.step+1; next[tail].num=head; next[tail++].operat=i; q.push(temp); } } else if(i==2){ //fill b if(p.bleft!=B&&!vis[p.aleft][B]){ vis[p.aleft][B]=1; temp.aleft=p.aleft; temp.bleft=B; temp.step=p.step+1; next[tail].num=head; next[tail++].operat=i; q.push(temp); } } else if(i==3){ //drop a; if(p.aleft&&!vis[0][p.bleft]){ vis[0][p.bleft]=1; temp.aleft=0; temp.bleft=p.bleft; temp.step=p.step+1; next[tail].num=head; next[tail++].operat=i; q.push(temp); } } else if(i==4){ //drop b; if(p.bleft&&!vis[p.aleft][0]){ vis[p.aleft][0]=1; temp.bleft=0; temp.aleft=p.aleft; temp.step=p.step+1; next[tail].num=head; next[tail++].operat=i; q.push(temp); } } else if(i==5){ // pour(1,2) if(p.bleft!=B&&p.aleft){ if(p.aleft>B-p.bleft&&!vis[p.aleft-B+p.bleft][B]){ vis[p.aleft-B+p.bleft][B]=1; temp.aleft=p.aleft-B+p.bleft; temp.bleft=B; temp.step=p.step+1; next[tail].num=head; next[tail++].operat=i; q.push(temp); } else if(p.aleft<=B-p.bleft&&!vis[0][p.bleft+p.aleft]){ vis[0][p.bleft+p.aleft]=1; temp.aleft=0; temp.bleft=p.bleft+p.aleft; temp.step=p.step+1; next[tail].num=head; next[tail++].operat=i; q.push(temp); } } } else if(i==6){ //pour (2,1) if(p.aleft!=A&&p.bleft){ if(p.bleft>A-p.aleft&&!vis[A][p.bleft-A+p.aleft]){ vis[A][p.bleft-A+p.aleft]=1; temp.aleft=A; temp.bleft=p.bleft-A+p.aleft; temp.step=p.step+1; next[tail].num=head; next[tail++].operat=i; q.push(temp); } else if(p.bleft<=A-p.aleft&&!vis[p.aleft+p.bleft][0]){ vis[p.aleft+p.bleft][0]=1; temp.bleft=0; temp.aleft=p.bleft+p.aleft; temp.step=p.step+1; next[tail].num=head; next[tail++].operat=i; q.push(temp); } } } } head++; } if(f==0) puts("impossible"); } int main(){ int a,b,c; while(~scanf("%d%d%d",&a,&b,&c)) bfs(a,b,c); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator