POJ 3278 Catch That Cow

题目链接：POJ 3278 【atch That Cow】

思路

       将起点放入队列，然后一次取出队列中的元素，对其进行左右移动和乘2的移动，并判断移动后的位置是否合法，合法则放入队列中继续操作。每次取出队列中的元素后，通过假设剩下的步骤全部是左右移动一格来更新结果。

代码

#include <iostream>
#include <stdlib.h>
#include <queue>
#include <cmath>
using namespace std;
#define ll long long
const int N = 1e5 + 10;

int n, k, dir[2] = {1, -1};
bool vis[N];

bool check(int x) {
  if (x >= 0 && x <= 100000 && vis[x] == false) 
    return true;
  else
    return false;
}

int bfs() {
  int res = 1e9;

  queue<pair<int, int> > q;
  q.push({n, 0});
  vis[n] = true;

  while (!q.empty()) {
    // 取出栈顶，并操作
    pair<int, int> d = q.front();
    q.pop();

    // 更新结果
    res = min(res, abs(k - d.first) + d.second);

    // 左右移动
    for (int i = 0; i < 2; i++) {
      pair<int, int> dd = d;
      dd.first += dir[i];
      dd.second++;
      // 当前位置未被访问且在范围内时，将当前位置加入队列中，并标记当前位置已经被使用过
      if (check(dd.first) == true) {
        q.push(dd);
        vis[dd.first] = true;
      }
    }

    // 乘2移动
    pair<int, int> dd = d;
    dd.first *= 2;
    dd.second++;
    if (check(dd.first) == true) {
      q.push(dd);
      vis[dd.first] = true;
    }
  }

  return res;
}

int main() {
  cin >> n >> k;
  
  cout << bfs() << endl;

  return 0;
}