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

POJ 3278 Catch That Cow 这道题不知哪错了,请指教一下,看了好多代码,多谢了!!

Posted by wanglinlin123 at 2012-03-12 21:53:09
这道题不知道拿错了,看了很多别人的代码,思路一样,实现的方法也有一样但是就是WA了,测试了很多数据,都对。请大家帮忙看看。多谢了
#include <stdio.h>

#define MAX 200009
struct node
{
	int depth;         //这是用来记录步数的或者说是第几层
	int data;          //这是用来记录生成的数据的。
}q[MAX];
int flag[MAX];
int front,rear;
int n,k;

void bfs()
{
	int e,ddepth=0;
	front=rear=0;
	flag[n]=1;
	rear=(rear+1)%MAX;
	q[rear].data=n;
	q[rear].depth=ddepth;
	while(front!=rear)
	{
		front=(front+1)%MAX;
		e=q[front].data;
		ddepth=1+q[front].depth;  //ddepth是用来记录即将要生成的几个数是第几层的(第几步的)。
		if(e==k)
		{
			printf("%d\n",q[front].depth);
			break;
		}
		else                              //三种操作及相应的剪枝
		{
			if(e+1<(2*k-n)&&flag[e+1]==0)
			{
			  flag[e+1]=1;
			  rear=(rear+1)%MAX;
			  q[rear].data=e+1;
			  q[rear].depth=ddepth;
			}
			if(e-1>(n/2)&&flag[e-1]==0)
			{
				flag[e-1]=1;
				rear=(rear+1)%MAX;
				q[rear].data=e-1;
				q[rear].depth=ddepth;
			}
			if(e*2<(2*k-n)&&flag[e*2]==0)
			{
				flag[e*2]=1;
				rear=(rear+1)%MAX;
				q[rear].data=e*2;
				q[rear].depth=ddepth;
			}

		}
	}
}



void init()
{
	int i;
	for(i=0;i<=MAX;i++)
	{
		flag[i]=0;
		q[i].depth=0;
	}
}
int main()
{
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		init();
		if(n>=k)
		{
			printf("%d\n",n-k);
		}
		else
		{
			bfs();
		}
	}
	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