GREATESC - Editorial

Problem Link - The Great Escape

Problem Statement

Heroes in Indian movies are capable of superhuman feats. For example, they can jump between buildings, jump onto and from running trains, catch bullets with their hands and teeth and so on. A perceptive follower of such movies would have noticed that there are limits to what even the superheroes can do. For example, if the hero could directly jump to his ultimate destination, that would reduce the action sequence to nothing and thus make the movie quite boring. So he typically labours through a series of superhuman steps to reach his ultimate destination.

In this problem, our hero has to save his wife/mother/child/dog/… held captive by the nasty villain on the top floor of a tall building in the centre of Bombay/Bangkok/Kuala Lumpur/… Our hero is on top of a (different) building. In order to make the action “interesting” the director has decided that the hero can only jump between buildings that are “close” to each other. The director decides which pairs of buildings are close enough and which are not.

Given the list of buildings, the identity of the building where the hero begins his search, the identity of the building where the captive (wife/mother/child/dog…) is held, and the set of pairs of buildings that the hero can jump across, your aim is to determine whether it is possible for the hero to reach the captive. And, if he can reach the captive he would like to do so with the minimum number of jumps.

Here is an example. There are 5 buildings, numbered 1,2,...,5, the hero stands on building 1 and the captive is on building 4. The director has decided that buildings 1 and 3, 2 and 3, 1 and 3, 3 and 2, 3 and 5, and 4 and 5 are close enough for the hero to jump across. The hero can save the captive by jumping from 1 to 3 and then from 3 to 5 and finally from 5 to 4. (Note that if i and j are close then the hero can jump from i to j as well as from j to i.) In this example, the hero could have also reached 4 by jumping from 1 to 2, 2 to 3, 3 to 5 and finally from 5 to 4. The first route uses 3 jumps while the second one uses 4 jumps. You can verify that 3 jumps is the best possible. If the director decides that the only pairs of buildings that are close enough are 1 and 3, 1 and 2, and 4 and 5, then the hero would not be able to reach building 4 to save the captive.

Approach

The problem can be solved by finding the shortest path in an unweighted graph. Each building is a node, and the possible jumps (pairs of buildings that are close enough) form the edges between the nodes.

To find the shortest path from the hero’s starting building to the building where the captive is held, we use the Breadth-First Search (BFS) algorithm. BFS is ideal because it explores all nodes at the present “level” (distance) before moving on to nodes at the next level, guaranteeing that the first time we reach a node, it is via the shortest path.

Here’s how we approach the problem:

  1. Start BFS from the hero’s building, marking it as visited.

  2. Explore all buildings that are directly reachable from the current building.

  3. For each reachable building, keep track of how many jumps it took to get there.

  4. If we reach the building where the captive is held, the number of jumps is the shortest path. If we explore all buildings and cannot reach the captive, then the hero cannot save the captive.

BFS ensures that we always explore the shortest paths first. Since we check all possible paths level by level, we can guarantee that when we reach the captive’s building, we have done so with the minimum number of jumps.

Time Complexity

The time complexity is O(n + m), where n is the number of buildings (nodes) and m is the number of close pairs (edges), as BFS visits each node and edge once.

Space Complexity

The space complexity is O(n + m), as we store the adjacency list and track the jumps for each building.