poj Catch That Cow BFS 王道P141

//poj Catch That Cow   BFS 王道P141
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 1e5+10;

struct Status{
    int position;
    int time;
    Status(){} //此时不写系统会默认一个么？暂不理会
    Status(int p,int t):position(p),time(t){}
};

bool visit[MAXN];//自己：直接变为结构体Status一个字段不行么？
int BFS(int n,int k){
    queue<Status> myQueue;
    myQueue.push(Status(n,0));
    visit[n] = true;
    while(!myQueue.empty()){
        Status current = myQueue.front();
        //cout<<current.position<<"---"<<k<<endl;
        if(current.position == k){
            return current.time;
        }
        myQueue.pop();
        for(int i=0;i<3;++i){
            Status next = current;
            if(i==0){
                next.position -= 1;
            }else if(i==1){
                next.position += 1;
            }else{
                next.position *= 2;
            }
            next.time += 1;
            if(next.position < 0 || next.position> 1e5 || visit[next.position]){
                continue;
            }
            myQueue.push(next);
            visit[next.position] = true;

        }

    }
}

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    memset(visit,false, sizeof(visit));
    printf("%d\n",BFS(n,k));

    return 0;
}
//todo 自己尝试修改不行

//poj Catch That Cow   BFS 王道P141
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 1e5+10;

struct Status{
    int position;
    int time;
    bool visited;
//    Status(){} //此时不写系统会默认一个么？暂不理会
    Status(int p,int t,bool visited = false):position(p),time(t),visited(visited){}
};

//bool visit[MAXN];//自己：直接变为结构体Status一个字段不行么？
int BFS(int n,int k){

    queue<Status> myQueue;
    myQueue.push(Status(n,0,true));

    while(!myQueue.empty()){
        Status current = myQueue.front();
        cout<<current.position<<"---"<<k<<endl;
        if(current.position == k){
            return current.time;
        }
        myQueue.pop();
        for(int i=0;i<3;++i){
            Status next = current;
            if(i==0){
                next.position -= 1;
            }else if(i==1){
                next.position += 1;
            }else{
                next.position *= 2;
            }
            next.time += 1;
            if(next.position < 0 || next.position> 1e5 || next.visited){
                continue;
            }
            next.visited = true; //放在myQueue.push(next)编译器显示不行？？
            myQueue.push(next);


        }

    }
}

int main(){
    int n,k;
    scanf("%d%d",&n,&k);

    printf("%d\n",BFS(n,k));

    return 0;
}