HDOJ/HDU 2717 Catch That Cow 1次元広度優先検索so easuy……

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=2717
考え方:毎回3つの方向があって、1をプラスして、1を減らして、2に乗って、境界の条件に注意して、1を減らして0より小さくなることができなくて、2に乗って最大の値を上回ることができません.
そしてN>=Kに気をつけなければならない時は、1を減らせば到着できません.
 

#include <iostream>

#include <string>

#include <cstdio>

#include <cmath>

#include <vector>

#include <algorithm>

#include <sstream>

#include <cstdlib>

#include <fstream>

#include <queue>

using namespace std;

struct node{

	int pos,step;

}p,q;

int N,K,mmin;

bool visit[200010];

void bfs()

{

	queue<node> Q;

	memset(visit,0,sizeof(visit));

	p.pos=N;

	p.step=0;

	Q.push(p);

	visit[N]=1;

	while(!Q.empty())

	{

		p=Q.front();

		Q.pop();

		if(p.pos==K){

			if(p.step<mmin)mmin=p.step;

		}

		for(int i=0;i<3;i++)

		{

			if(i==0){         //x+1； 

				if(p.pos>K)

					continue; 

				q.pos=p.pos+1;

				if(visit[q.pos])continue;

				q.step=p.step+1;

				Q.push(q);	

				visit[q.pos]=1;

			}

			else if(i==1){    //x-1; 

			



				q.pos=p.pos-1;

				if(visit[q.pos])continue;

				if(q.pos<0)continue;

				q.step=p.step+1;

				Q.push(q);

				visit[q.pos]=1;

			}

			else if(i==2){    //2*x;

				if(p.pos>K)continue;

				q.pos=2*p.pos;

				if(visit[q.pos])continue;

				if(q.pos>100000)continue;

				q.step=p.step+1;

				Q.push(q);

				visit[q.pos]=1;

			}

			

		}

	}

}

int main()

{

	//ifstream fin;

	//fin.open("data1.txt");

	while(cin>>N>>K)

	{

		mmin=99999;

		if(N>=K){

			cout<<N-K<<endl;

		}

		else {

			bfs();

			cout<<mmin<<endl;

		}

			

		

	}

	

	return 0;



}