POJ - 3278 Catch That Cow 【BFS】

题目链接

http://poj.org/problem?id=3278

题意

给出两个数字 N K 每次 都可以用三个操作 + 1 - 1 * 2

求 最少的操作次数 使得 N 变成 K

思路

BFS 但是要注意 设置 数组的范围 小心 RE

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <list>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a, b) memset(a, (b), sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1.0);

const double E = exp(1.0);

const double eps = 1e-8;

const int INF = 0x3f3f3f3f;

const int maxn = 2e5 + 5;

const int MOD = 1e9 + 7;

int n, k;

int ans;

int v[maxn];

struct node

{

    int v, step;

};

bool ok(int x)

{

    if (x < 0 || x > maxn)

        return false;

    return true;

}

void bfs()

{

    CLR(v, 0);

    queue <node> q;

    node tmp;

    tmp.v = n;

    tmp.step = 0;

    q.push(tmp);

    v[n] = 1;

    while (!q.empty())

    {

        node u = q.front(), V;

        q.pop();

        if (u.v == k)

        {

            ans = u.step;

            return;

        }

        V.step = u.step + 1;

        V.v = u.v + 1;

        if (ok(V.v) && v[V.v] == 0)

        {

            q.push(V);

            v[V.v] = 1;

        }

        V.v = u.v - 1;

        if (ok(V.v) && v[V.v] == 0)

        {

            q.push(V);

            v[V.v] = 1;

        }

        V.v = u.v * 2;

        if (ok(V.v) && v[V.v] == 0)

        {

            q.push(V);

            v[V.v] = 1;

        }

    }

}

int main()

{

    scanf("%d%d", &n, &k);

    ans = INF;

    bfs();

    cout << ans << endl;

}