Indian Computing Olympiad

Basic Graph Algorithms→Prisoners escape (Baltic Olympiad 2007)

A group of war prisoners are trying to escape from a prison. They have thoroughly planned the escape from the prison itself, and after that they hope to find shelter in a nearby village. However, the village (marked as B, see picture below) and the prison (marked as A) are separated by a canyon which is also guarded by soldiers (marked as S). These soldiers sit in their pickets and rarely walk; the range of view of each soldier is limited to exactly 100 meters. Thus, depending on the locations of soldiers, it may be possible to pass the canyon safely, keeping the distance to the closest soldier strictly larger than 100 meters at any moment.

                         Mountains
          ------------------------------------------------
          |                  S                  S
          |       S
       A  |                        S                         B
          |                S
          |                                S
          ------------------------------------------------
                         Mountains
      

Given the width and the length of the canyon and the coordinates of every soldier in the canyon, and assuming that soldiers do not change their locations, you have to determine whether prisoners can pass the canyon unnoticed.

Model this as a graph. Each soldier is a vertex. Two soldiers are adjacent if they are at most distance 200 apart (there is no way to go between them).

Add a vertex s for the top boundary of the canyon and a vertex t for the bottom boundary. A soldier is adjacent to s if it is within 100 of the top border. A soldier is adjacent to t if it is within 100 of the bottom border.

Claim: If there is a sequence of guards that connect the top border to the bottom border in this graph, there is no way to escape. Otherwise, we can find a route that goes between the soldiers.

Hence, the solution just requires checking whether t is reachable from s in this graph.

---