link:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=353#problem/D

是道广搜的题,值得纪念一下~~
给出起点和终点,有三种走法,x-1,x+1,2*x,问最少次数~~
只要跟着这个思路创建队列就好了~~
code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define N 100100
using namespace std;

int visit[N];/*记录是否已经走过*/
int count[N];/*记录每一次的步数*/

int main()
{
    int n,k,front;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        queue<int>q;
        memset(visit,0,sizeof(visit));
        memset(count,0,sizeof(count));
        q.push(n);/*起始点*/
        visit[n]=1;/*起始点记录访问*/
        while(!q.empty())/*队列不为空*/
        {
            front=q.front();/*出队列*/
            q.pop();
            /*以下为三种走法,即三个邻接点x-1,x+1,x*2*/
            if(visit[front-1]==0&&front-1<=100000&&front-1>=0)/*如果未曾访问,且在数组范围内*/
            {
                visit[front-1]=1;/*访问*/
                q.push(front-1);/*进队列*/
                count[front-1]=count[front-1]+count[front]+1;/*记录次数*/
            }
            if(visit[front+1]==0&&front+1<=100000&&front+1>=0)
            {
                visit[front+1]=1;
                q.push(front+1);
                count[front+1]=count[front+1]+count[front]+1;
            }
            if(visit[front*2]==0&&front*2<=100000&&front*2>=0)
            {
                visit[front*2]=1;
                q.push(front*2);
                count[front*2]=count[front*2]+count[front]+1;
            }
        }
        printf("%d\n",count[k]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation