Indian Computing Olympiad

Basic Graph Algorithms

Reachability in a grid

To motivate the need to use graphs, we examine the following problem

The Great Escape (IARCS Online Contest, Oct 2004)

Heroes in Tamil 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 whose height is within 10 metres.

Given the arrangement of buildings and their heights, your aim is determine whether it is possible for the hero to reach the captive.

Here is an example where the goal is to get from the top left building to the bottom right building.

            70    80    80    70

            60    30    20    30

            50    40    10    50

            45    60    20    10
      

Here is a possible path:

            70    80    80    70
             |
            60    30 -- 20    30
             |     |     |
            50 -- 40    10    50
                         |
            45    60    20 -- 10
      

Finding a path

How do we find such a path? We systematically calculate all the buildings that are reachable. For each building, we know (by the heights) which of the neighbouring buildings can be reached in one step.

• Initially, the starting position (1,1) is reachable
• If (i,j) is reachable, (i',j') is a neighbour of (i,j) and the height difference is at most 10, then (i',j') is also reachable.

Using this procedure, we can grow the set of all reachable buildings until we cannot add any more buildings. At this point, we check if the target building is in the reachable set.

How do we code this? Here is a recursive solution:

• Building heights are stored in a matrix A[N][N]
• Currently reachable buildings are in a matrix Mark[N][N], initialized to 0

        check(i,j){ // Assuming that (i,j) has just been marked, n
                    // mark all its neighbours
           if ((i-1,j) within grid &&             // Nbr within grid
               abs(A[i-1][j] - A[i][j] <= 10) &&  // Difference is OK
               Mark[i-1][j] == 0){                // Nbr unmarked

               Mark[i-1][j] = 1;
               check(i-1,j);
           }

           /* Similarly check (i+1,j), (i,j-1), (i,j+1) */

           ...
        }      
      

For each (i,j), check(i,j) is called at most once and processing check(i,j) takes constant time since each building has at most four neighbours, so this will take time proportional to N², the total number of buildings.

Finding the shortest route

What if, in addition, we want to compute the shortest route from (1,1) to (N,N)?

An efficient way to maintain and process marked positions is to use a queue (first-in-first-out collection).

• Initially, mark the starting position and add it to the queue.
• In each round:
  
  (Assume we have a queue of marked positions whose neighbours are yet to be explored.)
• Extract the first element from the queue. Mark all unmarked reachable neighbours (whose height difference is within the bound) and insert them into the queue.
• Repeat this till the queue becomes empty (there are no more marked positions to examine).

For instance:

            70    80    80    70

            60    30    20    30

            50    40    10    50

            45    60    20    10
      

• Mark (1,1) and start with Queue = {(1,1)}
• Extract (1,1) from head of queue, mark its reachable neighbours and add them to the Queue:
  Queue is now {(1,2),(2,1)}
• Extract (1,2) from head of queue, mark its reachable neighbours and add them to the Queue:
  Queue is now {(2,1),(1,3)}
• Extract (2,1) from head of queue, mark its reachable neighbours and add them to the Queue:
  Queue is now {(1,3),(3,1)}
• Extract (1,3) from head of queue, mark its reachable neighbours and add them to the Queue:
  Queue is now {(3,1),(1,4)}
• Extract (3,1) from head of queue, mark its reachable neighbours and add them to the Queue:
  Queue is now {(1,4),(3,2),(4,1)}
• …

Let us examine the order in which positions get marked. When we explore a position that is k steps away from the starting position, its neighbours are k+1 steps away and get added later in the queue. By maintaining the marked positions in the queue, we guarantee that positions are marked in increasing order of their distance from the source. We can also record the distance with each node as we visit it.

This method of exploration, in which we explore all neighbours level by level, is called breadth first search.

The earlier recursive formulation (using "check(i,j)") is depth first search. We pick a neigbhour to explore, then explore its neighbours, … till we can make no progress, and then we come back to process the next unmarked neighbour of the first node.

Here is a more precise formulation of breadth first search:

        Mark[(i,j)] = 0 for all (i,j)

        Mark[(1,1)] = 1;
        Dist[(1,1)] = 0;
        Insert (1,1) into the queue;

        BFS {
           while (queue is not empty) {
             v = head of queue;
             for each unmarked neighbour w of v {
               Mark[w] = 1;
               Dist[w] = Dist[v] + 1;
               Insert w into the queue;
             }
           }
        }