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

c++AC。粗暴型,附代码

Posted by xidianxlwang at 2017-05-18 00:22:09
#include<cstdio>
#include<queue>

using namespace std;

int N,K;

bool mark[100001];

struct E{
    int x;
    int t;
};

queue<E>Q;

int BFS(int x,int t)
{
    while(Q.empty()==false)
    {
        E now=Q.front();
        Q.pop();
        for(int i=0;i<3;i++)
        {
            if(i==0){
                int nx=now.x+1;
                if(nx<0||nx>100000||mark[nx]==true)continue;
                E tmp;
                tmp.x=nx;
                tmp.t=now.t+1;
                Q.push(tmp);
                mark[nx]=true;
                if(nx==K)return tmp.t;
            }
            else if(i==1){
                int nx=now.x-1;
                if(nx<0||nx>100000||mark[nx]==true)continue;
                E tmp;
                tmp.x=nx;
                tmp.t=now.t+1;
                Q.push(tmp);
                mark[nx]=true;
                if(nx==K)return tmp.t;
            }
            else if(i==2){
                int nx=2*now.x;
                if(nx<0||nx>100000||mark[nx]==true)continue;
                E tmp;
                tmp.x=nx;
                tmp.t=now.t+1;
                Q.push(tmp);
                mark[nx]=true;
                if(nx==K)return tmp.t;
            }

        }
    }
}

int main()
{
    for(int i=0;i<=100000;i++)
        mark[i]=false;
    scanf("%d%d",&N,&K);
    mark[N]=true;
    while(Q.empty()==false)Q.pop();
    E tmp;
    tmp.x=N;
    tmp.t=0;
    Q.push(tmp);
    int time=BFS(N,0);
    printf("%d",time);
    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