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

刚开始一直RE,是自己忘了改标记位,正常是0ms

Posted by 110120_119 at 2019-04-04 17:04:10 on Problem 3278
#include<cstdio>
#pragma warning (disable:4996)
using namespace std;

const int MAXN = 100001;

int N, K;
int minStep;			//最短步数
int visit[MAXN];		//访问标记数组,同一个点走两次一定不是最小步数

struct Node
{
	int x;				//当前位置
	int step;			//到达该位置已经走了多少步
}queue[MAXN];

void bfs()
{
	Node now, next;				//当前位置,下一个位置
	int head = 0, tail = 1;		//队列头尾指针

	now.x = N;		now.step = 0;
	queue[head] = now;			//初始状态入队
	visit[N] = 1;				//初始点标记

	while (head < tail)
	{
		now = queue[head];
		head++;

		if ((now.x + 1) < MAXN && visit[now.x+1]==0)
		{
			visit[now.x +1] = 1;
			next.x = now.x + 1;
			next.step = now.step + 1;
			queue[tail] = next;
			tail++;
			if (next.x == K)
			{
				minStep = next.step;
				return;
			}
		}
		if ((now.x - 1) >= 0 && visit[now.x-1]==0)
		{
			visit[now.x -1] = 1;
			next.x = now.x - 1;
			next.step = now.step + 1;
			queue[tail] = next;
			tail++;
			if (next.x == K)
			{
				minStep = next.step;
				return;
			}
		}
		if ((now.x * 2) < MAXN && now.x!=0 && visit[now.x*2]==0)
		{
			visit[now.x * 2] = 1;
			next.x = now.x * 2;
			next.step = now.step + 1;
			queue[tail] = next;
			tail++;
			if (next.x == K)
			{
				minStep = next.step;
				return;
			}
		}
	}
	
}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	while (scanf("%d %d", &N, &K) != EOF)
	{
		for (int i = 0; i < MAXN; i++)		//标记数组清零
			visit[i] = 0;

		bfs();
		printf("%d\n", minStep);
	}

	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