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

BFS+回溯打印 自我感觉代码还是蛮漂亮的(让各位见笑了。。)

Posted by NtNlyCoder at 2015-12-06 15:43:09 on Problem 3414
#include <cstdio>
#include <cstring>
#include <queue>
#define N 111
#define S 99
#define D1 -1
#define D2 -2
#define F1 1
#define F2 2
#define P12 12
#define P21 21
using namespace std;

class Path
{
	public:
		int x;
		int y;
};

class State
{
	public:
		int x;
		int y;
		int k;

		State(){}
		State(int initx,int inity,int initk)
			:x(initx),y(inity),k(initk){}
};

int A,B,C;
int v[N][N];
Path path[N][N];
queue<State> q;

void Init()
{
	memset(v,0,sizeof(v));
}

void Next(int x,int y,State cur,int mode)
{
	if(!v[x][y])
	{
		v[x][y] = mode;
		path[x][y].x = cur.x;
		path[x][y].y = cur.y;
		q.push(State(x,y,cur.k+1));
	}
}

State BFS()
{
	v[0][0] = S;
	path[0][0].x = -1;
	path[0][0].y = -1;
	q.push(State(0,0,0));
	State cur;
	while(q.size())
	{
		cur = q.front();
		q.pop();

		if(cur.x==C||cur.y==C)
		{
			while(q.size())
			{
				q.pop();
			}
			return cur;
		}

		Next(0,cur.y,cur,D1);
		Next(cur.x,0,cur,D2);
		Next(A,cur.y,cur,F1);
		Next(cur.x,B,cur,F2);
		int rx = A - cur.x;
		int ry = B - cur.y;
		if(cur.x<=ry)
		{
			Next(0,cur.y+cur.x,cur,P12);
		}
		else
		{
			Next(cur.x-ry,B,cur,P12);
		}
		if(cur.y<=rx)
		{
			Next(cur.x+cur.y,0,cur,P21);
		}
		else
		{
			Next(A,cur.y-rx,cur,P21);
		}
	}
	return State(-1,-1,-1);
}

void PrintPath(int x,int y,int k)
{
	if(!k)
	{
		return;
	}
	PrintPath(path[x][y].x,path[x][y].y,k-1);
	switch(v[x][y])
	{
		case D1:
			printf("DROP(1)\n");
			break;
		case D2:
			printf("DROP(2)\n");
			break;
		case F1:
			printf("FILL(1)\n");
			break;
		case F2:
			printf("FILL(2)\n");
			break;
		case P12:
			printf("POUR(1,2)\n");
			break;
		case P21:
			printf("POUR(2,1)\n");
			break;
	}
}

int main()
{
	Init();
	scanf("%d %d %d",&A,&B,&C);
	State ret = BFS();
	if(ret.k==-1)
	{
		printf("impossible\n");
	}
	else
	{
		printf("%d\n",ret.k);
		PrintPath(ret.x,ret.y,ret.k);
	}
}

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