HDOJ/HDU 2717 Catch That Cow 1次元広度優先検索so easuy……
1812 ワード
タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=2717
考え方:毎回3つの方向があって、1をプラスして、1を減らして、2に乗って、境界の条件に注意して、1を減らして0より小さくなることができなくて、2に乗って最大の値を上回ることができません.
そしてN>=Kに気をつけなければならない時は、1を減らせば到着できません.
考え方:毎回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;
}