现在的位置: 首页 > 综合 > 正文

POJ 3278

2013年03月19日 ⁄ 综合 ⁄ 共 756字 ⁄ 字号 评论关闭

半小时就写完了代码,提交后,一直是wa,煎熬了两小时后发现,忘了考虑在同一点这一情况

#include <stdio.h>
#include <memory.h>
const int maxn=200000+10;
int N,K;
int queue[maxn];
int visit[maxn]={0};
int dis[maxn];
int bfs(int N,int K)
{
	int font=0;
	int rear=0;
	queue[rear++]=N;
	visit[N]=1;
	int tem;
	while(font<rear)
	{
		int w=queue[font];
		int dist=dis[w];
		if(w==K) return dis[w];

		tem=w+1;
		if(tem>=0&&tem<=100000&&!visit[tem])
		
		{
			visit[tem]=1;
			dis[tem]=dist+1;
			queue[rear++]=tem;
			
		}
		tem=w-1;
		if(tem<=100000&&tem>=0&&!visit[tem])
		{
			visit[tem]=1;
			dis[tem]=dist+1;
			queue[rear++]=tem;
		}
		tem=w*2;
		if(tem>=0&&tem<=100000&&!visit[tem])
		{
			visit[tem]=1;
			dis[tem]=dist+1;
			queue[rear++]=tem;
		}
		font++;

	}
	
}
int main()
{


	while(scanf("%d",&N)!=EOF){
		scanf("%d",&K);
		memset(queue,0,sizeof(queue));
		memset(visit,0,sizeof(visit));
		memset(dis,0,sizeof(dis));
		printf("%d\n",bfs(N,K));
	}
	return 0;
}

抱歉!评论已关闭.