Catch That Cow#7748

Catch That Cow (Editorial)

We can consider the positions on the number line as vertices of a graph, and the possible movements as edges of this graph. For example, a step to the right represents an edge between vertices $x$ and $x + 1$ x + 1, while teleportation represents an edge between $x$ and $2 * x$ 2 * x.

The minimum number of minutes it takes for Farmer John to catch the escaped cow corresponds to the length of the shortest path between vertices $n$ and $k$ . To find this path, we use a breadth-first search starting from vertex $n$ . The answer is the shortest distance to vertex $k$ .

Example

Let’s look at the fastest route Farmer John can take to reach the cow: $5 \to 10 \to 9 \to 18 \to 17$ 5 → 10 → 9 → 18 → 17. This takes $4$ minutes.

Let’s now examine the step-by-step filling of the shortest distance array $d i s t$ .

Algorithm implementation

Declare the array $d i s t$ to store the shortest distances and a queue $q$ to perform the breadth-first search.

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

The go function handles the transition from vertex $v$ to vertex $t o$ . If $d i s t [t o] \neq = - 1$ dist[to] \ne -1, it means that the vertex to has already been visited, and there is no need to visit it again.

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

If the vertex $t o$ is not visited yet, add it to the queue $q$ and update the value of $d i s t [t o]$ dist[to] by adding one to the distance from vertex $v$ .

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

The function bfs implements a breadth-first search starting from the vertex $s t a r t$ .

void bfs(int start)
{

Initialize the data necessary for the breadth-first search.

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

Start the main loop, which continues until the queue becomes empty.

  while (!q.empty())
  {

Extract vertex $x$ from the front of the queue.

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

If the position $k$ , where the cow is located, is reached, terminate the search.

    if (x == k) return;

Consider all possible moves — to the right, to the left, and teleportation. If a move is possible, update the corresponding arrays.

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

The main part of the program. Read the input data. Run a breadth-first search starting from position $n$ . Print the answer — the minimum number of minutes it takes for Farmer John to reach position $k$ .

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