Poj3278-Catch That Cow-(BFS入门)

发布于 2019-07-21  1.14k 次阅读


问题传送门:

题意:

在X轴上,从一点x到另外一点的最少补数。
每一步有三种选择:x-1   x+1   x*2

分析:

一开始想贪心,但是想了许久没有想出一个很好的贪心策略。

其实是一道BFS入门题,

把每一点可以到达的三个点加入队列,顺序无所谓

因为BFS是一层一层的。

当某个可到达的点是终点时,BFS结束。

下面是代码:

#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 1e5+10;
queue <int> q;
int step[MAXN];
int vis[MAXN];

int BFS(int n, int k)
{
    int head, np;
    q.push(n);
    step[n] = 0;
    vis[n] = 1;
    while(!q.empty())
    {
        head = q.front();
        q.pop();
        for (int i = 0; i < 3; i++)
        {
            if (i == 0) np = head * 2;
            else if (i == 1) np = head -1;
            else           np = head +1;

            if (np < 0 || np >= MAXN || vis[np]) continue;
            
            q.push(np);
            vis[np] = 1;
            step[np] = step[head] + 1;
            if (np == k)
                return step[np];
        }
    }
    return 0;
}

int main()
{
    int n, k;
    cin >> n >> k;
    if (n >= k)
        cout << n-k << endl;
    else
        cout << BFS(n, k) << endl;

    return 0;
}

Simple And Clear