| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
刚开始一直RE,是自己忘了改标记位,正常是0ms#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator