抓牛 (catchcow. cpp/c/pas)

题目描述

农夫约翰被通知, 他的一只奶牛逃逸了! 所以他决定, 马上出发, 尽快把那只奶牛抓回来.

他们都站在数轴上．约翰在 \(N (0 \leq N \leq 100000)\) 处, 奶牛在 \(K (0 \leq K \leq 100000)\) 处. 约翰有两种办法移动, 步行和瞬移: 步行每秒种可以让约翰从 x 处走到 x+l 或 x-l 处; 而瞬移则可让他在 1 秒内从 x 处消失, 在 2x 处出现．然而那只逃逸的奶牛, 悲剧地没有发现自己的处境多么糟糕, 正站在那儿一动不动．

那么, 约翰需要多少时间抓住那只牛呢?

输入格式

仅有两个整数 N 和 K

输出格式

最短时间

样例输入

5 17

样例输出

4

Explanation

暴力贪心不可取~

我不会告诉你这道题用 BFS / DFS 的.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

using namespace std;
const int maxn = 100100;
const int infinit = 0x0f7f7f7f;

int n, k;
int dp[maxn];
bool inque[maxn];

int bfs(void)
{
    queue<int> que;
    for (int i = 0; i <= max(n, k) + 10; i++)
        dp[i] = infinit,
        inque[i] = false;
    que.push(n); inque[n] = true;
    dp[n] = 0;
    while (!que.empty()) {
        int p = que.front();
        que.pop();
        // printf("deque %d -> %d\n", p, dp[p]);
        if (p - 1 >= 0 && dp[p] + 1 < dp[p - 1]) {
            dp[p - 1] = dp[p] + 1;
            if (!inque[p - 1]) {
                que.push(p - 1);
                inque[p - 1] = true;
            }
        }
        if (p + 1 <= max(n, k) + 10 && dp[p] + 1 < dp[p + 1]) {
            dp[p + 1] = dp[p] + 1;
            if (!inque[p + 1]) {
                que.push(p + 1);
                inque[p + 1] = true;
            }
        }
        if (2 * p <= max(n, k) + 10 && dp[p] + 1 < dp[2 * p]) {
            dp[2 * p] = dp[p] + 1;
            if (!inque[2 * p]) {
                que.push(2 * p);
                inque[2 * p] = true;
            }
        }
        inque[p] = false;
    }
    return dp[k];
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &k);
    // I'm not using linear algorithm because it isn't correct. Use BFS instead.
    printf("%d\n", bfs());
    return 0;
}