POJ 3278==あの牛を捕まえろ
2122 ワード
// : (BFS)
#include
#include
#include
using namespace std;
int N, K;
const int MAXN = 100000 + 5;
int visited[2*(MAXN+10)];
struct Node{
int x;
int steps;
Node(int xx, int s) : x(xx), steps(s) {}
};
queue Q;
int main() {
cin >> N >> K;
memset(visited, 0, sizeof(visited));
Q.push(Node(N, 0));
visited[N] = 1;
while(!Q.empty()) {
Node temp = Q.front();
if(temp.x == K) {
//
cout << temp.steps << endl;
return 0;
}
else {
if(temp.x-1 >= 0 && !visited[temp.x-1]) {
visited[temp.x-1] = 1;
Q.push(Node(temp.x-1, temp.steps+1));
}
if(temp.x+1 <= MAXN && !visited[temp.x+1]) {
visited[temp.x+1] = 1;
Q.push(Node(temp.x+1, temp.steps+1));
}
if(temp.x*2 <= MAXN && !visited[temp.x*2]) {
visited[temp.x*2] = 1;
Q.push(Node(temp.x*2, temp.steps+1));
}
Q.pop();
}
}
return 0;
}
/*
// ( 100000 , 2 ) dfs
// !
#include
#include
#include
#include
#include