| ||||||||||
| 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 | |||||||||
Re:贴下代码留个纪念。In Reply To:贴下代码留个纪念。 Posted by:hello_hello at 2011-04-18 16:44:18 > #include<iostream>
> #include<cstring>
> #include<cstdio>
> #include<queue>
> using namespace std;
> struct node
> {
> int k;
> int a,b;
> int length;
> int pre;
> }f[10000];
> int A,B,C;
> int step,num;
> int visit[105][105];
> node start;
> int bfs()
> {
> memset(visit,0,sizeof(visit));
> int rear=0;
> int front=1;
> f[rear]=start;
> visit[start.a][start.b]=1;
> while(rear!=front)
> {
> node p=f[rear];
> // printf("%d %d\n",p.a,p.b);
> if(p.a==C || p.b==C)
> {
> step=p.length;
> num=rear;
> return 1;
> }
> node q;
> q=p;
> q.a=A;
> q.length=p.length+1;
> if(!visit[q.a][q.b] && p.a!=A)
> {
> visit[q.a][q.b]=1;
> q.pre=rear;
> q.k=1;
> f[front]=q;
> front++;
> }
> q=p;
> q.b=B;
> q.length=p.length+1;
> if(!visit[q.a][q.b] && p.b!=B)
> {
> visit[q.a][q.b]=1;
> q.pre=rear;
> q.k=2;
> f[front]=q;
> front++;
> }
> q=p;
> q.a=0;
> q.length=p.length+1;
> if(!visit[q.a][q.b] && p.a!=0)
> {
> visit[q.a][q.b]=1;
> q.pre=rear;
> q.k=3;
> f[front]=q;
> front++;
> }
> q=p;
> q.b=0;
> q.length=p.length+1;
> if(!visit[q.a][q.b] && p.b!=0)
> {
> visit[q.a][q.b]=1;
> q.pre=rear;
> q.k=4;
> f[front]=q;
> front++;
> }
> if(p.a!=A && p.b!=0)
> {
> q=p;
> if(q.a+q.b>=A)
> {
> q.a=A;
> q.b=(p.a+p.b)-A;
> }
> else
> {
> q.a+=q.b;
> q.b=0;
> }
> q.length=p.length+1;
> if(!visit[q.a][q.b])
> {
> visit[q.a][q.b]=1;
> q.pre=rear;
> q.k=5;
> f[front]=q;
> front++;
> }
> }
> if(p.b!=B && p.a!=0)
> {
> q=p;
> if(q.b+q.a>=B)
> {
> q.b=B;
> q.a=(p.a+p.b)-B;
>
> }
> else
> {
> q.b+=q.a;
> q.a=0;
> }
> q.length=p.length+1;
> if(!visit[q.a][q.b])
> {
> visit[q.a][q.b]=1;
> q.pre=rear;
> q.k=6;
> f[front]=q;
> front++;
> }
> }
> rear++;
> }
> return 0;
> }
> int main()
> {
> while(scanf("%d %d %d",&A,&B,&C)!=EOF)
> {
> start.a=0;
> start.b=0;
> start.pre=-1;
> start.length=0;
> int ans;
> ans=bfs();
> if(ans)
> {
> int m=num;
> printf("%d\n",step);
> int a[1000];
> int s=0;
> while(f[m].pre!=-1)
> {
> a[s++]=m;
> m=f[m].pre;
> }
> for(int i=s-1;i>=0;i--)
> {
> int k=f[a[i]].k;
> if(k==1)
> printf("FILL(1)\n");
> else if(k==2)
> printf("FILL(2)\n");
> else if(k==3)
> printf("DROP(1)\n");
> else if(k==4)
> printf("DROP(2)\n");
> else if(k==5)
> printf("POUR(2,1)\n");
> else if(k==6)
> printf("POUR(1,2)\n");
> m=f[m].pre;
> }
>
>
> }
> else
> 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