POJ 3278 Catch That Cow（BFS）

POJ 3278 Catch That Cow

​ 现在你在一个数轴上的位置 x，位置 k 上有一头牛，你要抓住这头牛，也就是走到位置 k 上。那怎么走呢？你有两种走路的方法，一种是从 x 移动到 \(2 \times x\)；一种是从 x 移动到 \(x - 1\)或者\(x + 1\)，他们都算是一步。假设牛不会动，请问你最少需要多少步能抓住这头牛。

思路：

​ 很经典的BFS模型嘛，转移也给好了。注意处理一下边界，以免越界。

代码：

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N = 100010;

int n, k;
int dis[N];
int vis[N];

struct node
{
    int x, step;
    node(int _x, int _step) {
        x = _x, step = _step;
    }
};


void bfs(int x)
{
    memset(vis, 0, sizeof vis);
    queue<node> q;  
    q.push(node(x, 0));
    vis[x] = 1;
    
    while(q.size())
    {
        node t = q.front();
        q.pop();

        if(t.x == k)   
        {
            cout << t.step << '\n';
            return;
        } 

        for(int i = 0; i < 3; i++)
        {
            int xx;
            if(i == 0)  xx = t.x + 1;
            else if(i == 1) xx = t.x - 1;
            else if(i == 2) xx = t.x * 2;

            if(xx >= 0 && xx <= N && !vis[xx])
            {
                q.push(node(xx, t.step + 1));
                vis[xx] = 1;
            }
        }
    }
}

int main()
{
    cin >> n >> k;
    bfs(n);
}