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<algorithm> #include<queue> using namespace std; struct node1 { int v1; int v2; }; struct node2 { int a; int b; int dir; }path[101][101]; int a,b,c; int flag=0; int map[101][101]; int result[101][101]; int BFS() { node1 k1,k2; queue<node1>q; k1.v1=0; k1.v2=0; path[0][0].a=0; path[0][0].b=0; path[0][0].dir=0; result[0][0]=0; map[0][0]=1; q.push(k1); while(!q.empty()) { k2=q.front(); q.pop(); if(k2.v1==c) { flag=1; return k2.v2; } if(k2.v2==c) { flag=2; return k2.v1; } k1.v1=a; k1.v2=k2.v2; if(k2.v1<a&&!map[k1.v1][k1.v2]) { map[k1.v1][k1.v2]=1; q.push(k1); result[k1.v1][k1.v2]=result[k2.v1][k2.v2]+1; path[k1.v1][k1.v2].a=k2.v1; path[k1.v1][k1.v2].b=k2.v2; path[k1.v1][k1.v2].dir=1; } k1.v1=k2.v1; k1.v2=b; if(k2.v2<b&&!map[k1.v1][k1.v2]) { map[k1.v1][k1.v2]=1; q.push(k1); result[k1.v1][k1.v2]=result[k2.v1][k2.v2]+1; path[k1.v1][k1.v2].a=k2.v1; path[k1.v1][k1.v2].b=k2.v2; path[k1.v1][k1.v2].dir=2; } k1.v1=0; k1.v2=k2.v2; if(k2.v1!=0&&!map[k1.v1][k1.v2]) { map[k1.v1][k1.v2]=1; q.push(k1); result[k1.v1][k1.v2]=result[k2.v1][k2.v2]+1; path[k1.v1][k1.v2].a=k2.v1; path[k1.v1][k1.v2].b=k2.v2; path[k1.v1][k1.v2].dir=3; } k1.v1=k2.v1; k1.v2=0; if(k2.v2!=0&&!map[k1.v1][k1.v2]) { map[k1.v1][k1.v2]=1; q.push(k1); result[k1.v1][k1.v2]=result[k2.v1][k2.v2]+1; path[k1.v1][k1.v2].a=k2.v1; path[k1.v1][k1.v2].b=k2.v2; path[k1.v1][k1.v2].dir=4; } k1.v1=0; k1.v2=k2.v1+k2.v2; if(k2.v1+k2.v2<=b&&!map[k1.v1][k1.v2]) { map[k1.v1][k1.v2]=1; q.push(k1); result[k1.v1][k1.v2]=result[k2.v1][k2.v2]+1; path[k1.v1][k1.v2].a=k2.v1; path[k1.v1][k1.v2].b=k2.v2; path[k1.v1][k1.v2].dir=5; } k1.v1=k2.v1+k2.v2-b; k1.v2=b; if(k2.v1+k2.v2>b&&!map[k1.v1][k1.v2]) { map[k1.v1][k1.v2]=1; q.push(k1); result[k1.v1][k1.v2]=result[k2.v1][k2.v2]+1; path[k1.v1][k1.v2].a=k2.v1; path[k1.v1][k1.v2].b=k2.v2; path[k1.v1][k1.v2].dir=5; } k1.v1=k2.v1+k2.v2; k1.v2=0; if(k2.v1+k2.v2<=a&&!map[k1.v1][k1.v2]) { map[k1.v1][k1.v2]=1; q.push(k1); result[k1.v1][k1.v2]=result[k2.v1][k2.v2]+1; path[k1.v1][k1.v2].a=k2.v1; path[k1.v1][k1.v2].b=k2.v2; path[k1.v1][k1.v2].dir=6; } k1.v1=a; k1.v2=k2.v1+k2.v2-a; if(k2.v1+k2.v2>a&&!map[k1.v1][k1.v2]) { map[k1.v1][k1.v2]=1; q.push(k1); result[k1.v1][k1.v2]=result[k2.v1][k2.v2]+1; path[k1.v1][k1.v2].a=k2.v1; path[k1.v1][k1.v2].b=k2.v2; path[k1.v1][k1.v2].dir=6; } } return -1; } int main() { int v,ans,i; int step[10000]; int x,y; int len=1; int temp1,temp2; memset(map,0,sizeof(map)); scanf("%d%d%d",&a,&b,&c); v=BFS(); if(v==-1) { printf("impossible\n"); return 0; } if(flag==1) { ans=result[c][v]; printf("%d\n",ans); x=c; y=v; while(path[x][y].dir) { step[len++]=path[x][y].dir; temp1=x; temp2=y; x=path[temp1][temp2].a; y=path[temp1][temp2].b; } } if(flag==2) { ans=result[v][c]; printf("%d\n",ans); x=v; y=c; while(path[x][y].dir) { step[len++]=path[x][y].dir; temp1=x; temp2=y; x=path[temp1][temp2].a; y=path[temp1][temp2].b; } } for(i=ans;i>=1;i--) { switch(step[i]) { 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; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator