Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

打酱油路过,贴下代码。

Posted by bingshen at 2010-07-20 13:20:50 on Problem 3414
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator