First time here? Checkout the FAQ!
+1 vote

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 (92.5k points) 967 2328 3115 | 30 views

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23346 Points

  2. Bikram

    17058 Points

  3. Habibkhan

    8142 Points

  4. srestha

    6254 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4968 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4298 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points

Recent Badges

100 Club Vamp thehacker
Popular Question LavTheRawkstar
Notable Question shubham vashishtha
Nice Answer Habibkhan
Good Question jenny101
Regular Ashish Subscription
Famous Question Akash Kanase
Photogenic guptasaurabh9868
Nice Question Nishant Arora
Notable Question gabbar
27,301 questions
35,153 answers
33,244 users