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 await8157 at 2013-02-04 15:56:05 on Problem 3414
#include <iostream>
#include <queue>
using namespace std;
struct point
{
	int a,b;
	int t;
	int step;
	point * pre;
};
bool vis[103][103];
char str[6][10]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int a,b,c,ta,tb;
point now;
int bfs();

void print(point now)
{
	if(now.pre!=NULL)
		print(*now.pre);
	cout<<str[now.t]<<endl;
};

int main()
{
	while(cin>>a>>b>>c)
	{
		memset(vis,false,sizeof(vis));
		cout<<bfs()<<endl;
	}
	return 0;
}

int bfs()
{
	queue<point>q;
	point start,node;
	start.a=0;
	start.b=0;
	start.step=0;
	start.pre=NULL;
	q.push(start);
	int step,x,y;
	while (!q.empty())
	{
		start=q.front();
		q.pop();
		x=start.a;
		y=start.b;
		step=start.step;
		if(x==c||y==c) { print(start);return step;}
		for(int i=0;i<6;i++)
		{
			if(i==0) 
			{ ta=a;tb=y;}
			if(i==1) 
			{ ta=x;tb=b;}
			if(i==2) 
			{ ta=0;tb=y;}
			if(i==3) 
			{ ta=x;tb=0;}
			if(i==4)
			{ if(b-y>=x) 
				{ ta=0;tb=x+y; }
				else
				{ ta=x+y-b;tb=b; }
			}
			if(i==5)
			{ if(a-x>=y) 
				{ ta=x+y;tb=0; }
				else
				{ ta=a; tb=x+y-a; }
			}
			if(!vis[ta][tb])
				{ 
					node.a=ta;
					node.b=tb;
					node.t=i;
					node.step=step+1;
					node.pre=&start;
					q.push(node);
					vis[ta][tb]=true;
				}
			
		}
	
	}
	cout << "impossible" << endl;
}

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