Злови цю корову (Розбір)

Абсциси на координатній прямій можна розглядати як вершини графа, а способи пересування — як ребра цього графа. Наприклад, крок праворуч задає ребро між вершинами $x$ та x + 1, а телепортація — ребро між $x$ та 2 * x.

Мінімальна кількість хвилин, за яку фермер Джон зможе зловити втіклу корову, відповідає довжині найкоротшого шляху між вершинами $n$ та $k$. Для його знаходження скористаємося пошуком у ширину, починаючи з вершини $n$. Відповіддю є найкоротша відстань до вершини $k$.

Приклад

Розгляньмо найшвидший маршрут, яким фермер Джон може дістатися до корови: 5 → 10 → 9 → 18 → 17. Це займає $4$ хвилини.

Розгляньмо покрокове заповнення масиву найкоротших відстаней $dist$.

Реалізація алгоритму

Оголосимо масив найкоротших відстаней $dist$ та чергу $q$ для виконання пошуку у ширину.

#define MAX 200001
int dist[MAX];
queue<int> q;

Функція go відповідає за перехід з вершини $v$ в вершину $to$. Якщо dist[to] \ne -1, то вершина $to$ уже була відвідана раніше, і повторно в неї заходити не потрібно.

void go(int v, int to)
{
  if (dist[to] != -1) return;

Якщо вершина $to$ ще не відвідувалась, додаємо її в чергу $q$ і оновлюємо значення dist[to], додавши одиницю до відстані від вершини $v$.

  q.push(to);
  dist[to] = dist[v] + 1;
}

Функція bfs реалізує пошук у ширину, починаючи з вершини $start$.

void bfs(int start)
{

Ініціалізуємо дані, необхідні для пошуку у ширину.

  memset(dist, -1, sizeof(dist));
  dist[start] = 0;
  q.push(start);

Починаємо основний цикл, який триває доти, доки черга не стане пустою.

  while (!q.empty())
  {

Витягуємо вершину $x$ з початку черги.

    int x = q.front(); q.pop();

Якщо досягнуто позицію $k$, де знаходиться корова, завершуємо пошук.

    if (x == k) return;

Розглядаємо всі можливі способи пересування — вправо, вліво та телепортацію. Якщо перехід можливий, оновлюємо відповідні масиви.

    if (x + 1 < MAX) go(x, x + 1);
    if (x - 1 >= 0) go(x, x - 1);
    if (2 * x < MAX) go(x, 2 * x);
  }
}

Основна частина програми. Читаємо вхідні дані. Запускаємо пошук у ширину з позиції $n$. Виводимо відповідь — мінімальну кількість хвилин, за яку фермер Джон зможе дістатися до позиції $k$.

scanf("%d %d", &n, &k);
bfs(n);
printf("%d\n", dist[k]);