Bu inəyi tut (Həll təhlili)

Koordinat düz xəttindəki absissaları qrafın zirvələri kimi, hərəkət üsullarını isə qrafın kənarları kimi nəzərdən keçirə bilərik. Məsələn, sağa addım atmaq $x$ və x + 1 zirvələri arasında bir kənar qurur, teleportasiya isə $x$ və 2 * x arasında bir kənar qurur.

Fermer Conun qaçmış inək tutması üçün lazım olan minimal dəqiqələr sayı $n$ və $k$ zirvələri arasında olan ən qısa yolun uzunluğuna uyğundur. Bu yolun tapılması üçün zirvə $n$-dən başlayaraq genişlik üzrə axtarışdan istifadə edək. Cavab kimi $k$ zirvəsinə olan ən qısa məsafə veriləcək.

Nümunə

Fermer Conun inəyə çatmağın ən sürətli yolunu nəzərdən keçirək: 5 → 10 → 9 → 18 → 17. Bu $4$ dəqiqə çəkir.

Gəlin, qısa məsafə ilə $dist$ massivinin ardıcıl doldurulmasına baxaq.

Alqoritmin təcrübi tətbiqi

Qısa məsafələrin $dist$ massivini və genişlik üzrə axtarış üçün növbəni $q$ elan edək.

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

go funksiyası $v$ zirvəsindən $to$ zirvəsinə keçməyi təmin edir. Əgər dist[to] ≠ -1 olarsa, $to$ zirvəsi artıq ziyarət edilib və yenidən ora getməyə ehtiyac yoxdur.

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

Əgər $to$ zirvəsi hələ ziyarət olunmayıbsa, onu növbəyə $q$ daxil edirik və dist[to] dəyərini $v$ zirvəsindən olan məsafəyə bir əlavə edərək yeniləyirik.

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

bfs funksiyası $start$ zirvəsindən başlayaraq genişlik üzrə axtarışı həyata keçirir.

void bfs(int start)
{

Genişlik üzrə axtarış üçün zəruri olan məlumatları inicializasiya edirik.

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

Əsas dövrəyə başlayırıq, növbə boş olmadıqca davam edirik.

  while (!q.empty())
  {

Növbənin başlanğıcından $x$ zirvəsini çıxarırıq.

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

Əgər inəyi tutmalı olan $k$ mövqeyinə çatılarsa, axtarışı dayandırırıq.

    if (x == k) return;

Bütün mümkün hərəkət üsullarını nəzərdən keçiririk — sağa, sola və teleportasiya. Əgər keçid mümkündürsə, uyğun massivləri yeniləyirik.

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

Proqramın əsas hissəsini. Giriş məlumatlarını oxuyuruq. $n$ mövqeyindən genişlik üzrə axtarışı başladırıq. Cavabı – fermer Conun $k$ mövqeyinə çatması üçün lazım olan minimal dəqiqələr sayını çap edirik.

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