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