| ||||||||||
| 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