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 chenxuan123456789 at 2012-09-06 21:04:35 on Problem 3278
#include <stdio.h>
#include <string.h>
#define l 100010
int flag[l*4];
int head,tail;
struct point
{
	int num;
	int cut;
};
struct point q[l];
int s,e;
void bfs()
{
	int temp;
	memset(flag,0,sizeof(flag));
	flag[s]=1;
	head=0;
	tail=0;
	q[head].num=s;
	q[head++].cut=0;
	while(head!=tail)
	{
		temp=q[tail].num;
		if(temp==e)
			break;
		else
		{
			if(temp-1>=0&&temp-1<=l&&!flag[temp-1])
			{
				flag[temp-1]=1;
				q[head].num=temp-1;
				q[head++].cut=q[tail].cut+1;
			}
			if(temp+1>=0&&temp+1<=l&&!flag[temp+1])
			{
				flag[temp+1]=1;
				q[head].num=temp+1;
				q[head++].cut=q[tail].cut+1;
			}
			if(2*temp>=0&&2*temp<=l&&!flag[2*temp])
			{
				flag[2*temp]=1;
				q[head].num=2*temp;
				q[head++].cut=q[tail].cut+1;
			}
		}
		tail++;
	}
	printf("%d\n",q[tail].cut);
}
int main()
{
	while(scanf("%d %d",&s,&e)!=EOF)
	{
		bfs();
	}
	return 1;
}

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