GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
23 views

A group of war prisoners are trying to escape from a prison. They have thoroughly planned teh 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 from any moment. The situation is depicted in the following picture, where the circles around $S$ indicate the range of view.

Provide an algorithm to determine if the prisoners  can pass the canyon unnoticed, given the width and the length of a canyon and teh coordinated of every soldier in the canyon, and assuming that soldiers do not change their locations ($Hint$: Model this as a graph, with soldiers represented by the vertices.)

asked in Others by Veteran (77.8k points)   | 23 views

Please log in or register to answer this question.



Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Arnab Bhadra

    1502 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1481 Points

  5. junaid ahmad

    1432 Points

  6. Debashish Deka

    1402 Points

  7. Rupendra Choudhary

    1226 Points

  8. rahul sharma 5

    1222 Points

  9. Arjun

    1168 Points

  10. pawan kumarln

    1164 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. pawan kumarln

    296 Points

  2. akankshadewangan24

    214 Points

  3. Arjun

    208 Points

  4. Debashish Deka

    156 Points

  5. Hira Thakur

    130 Points


23,414 questions
30,125 answers
67,508 comments
28,443 users