SPOJ.com - Problem PROG0169

PROG0169 - Manhattan

no tags

The Manhattan peninsula is one of the five boroughs of New York City. The borough is famous for its skyscrapers, broad avenues, the financial center Wall Street and the many yellow taxis that drive around the district. The streets of Manhattan are laid out in a rectangular grid by the Commissioners' Plan of 1811. The area is intersected by avenues (running north and south) and streets (running east and west).

Manhattan Commissioners' Plan

Consider a rectangular $s \times a$ grid that represent part of Manhattan covering $s$ streets and $a$ avenues. Taxis can refuel at a number of petrol stations located at various intersections. Whenever a taxi is close to running out of gasoline, its driver can read the coordinates of the closest petrol station from his GPS. Due to bad programming, however, there is a bug in the GPS devices of the taxis. If there are multiple "closest" petrol stations at a given intersection, the GPS gets lost, which panics the driver who then causes a car crash. Such intersections are therefore called critical points.

Assignment

In Manhattan, an intersection on a rectangular $s \times a$ grid is always represented as a tuple $(x, y)$, where $x, y \in \mathbb{N}$, $0 \leq x < s$ and $0 \leq y < a$. The intersection at the top left corner of the grid therefore is at position $(0, 0)$, and the intersection at the bottom right corner is at position $(s-1, a-1)$. This is also the representation of the intersections as they are used in this exercise.

In Manhattan, the distance between two intersections $(x_1, y_1)$ and $(x_2, y_2)$ is computed as $$|x_1 - x_2| + |y_1 - y_2|\,,$$ where $|x|$ represents the absolute value of $x$. This distance is called Manhattan distance (or city block distance) in literature. Write a function manhattanDistance that returns the Manhattan distance between two given intersections. The coordinates of both intersections must be passed as arguments to the function.
Use the function manhattanDistance to write a function critical that returns a Boolean value indicating whether or not a given intersection is at a critical point. Two arguments must be passed to this function: the coordinates of the intersection that must be evaluated, and a list of intersections at which the petrol stations are located on the $s \times a$ grid.
Write a function manhattan that takes three arguments: i) the number of streets $s$, ii) the number of avenues $a$, and iii) a list of intersections at which the petrol stations are located on the $s \times a$ grid. The function must print a representation of the rectangular grid, in which all intersections are by default represented with an asterisk (*). Intersections having a petrol station are represented with the letter P, and intersections that are at critical points are represented with the letter D.

Example

In the example $10\times 10$ grid that is represented in the following interactive Python session, the intersection at position $(5,0)$ is an example of a critical point, since there are two petrol stations at Fourth Avenue that are both at distance 4 from the intersection $(5,0)$.

>>> manhattanDistance((3, 5), (7, 9))
8
>>> manhattanDistance((12, 5), (3, 16))
20

>>> critical((4, 3), [(1, 8), (4, 3), (6, 3), (6, 5)])
False
>>> critical((7, 4), [(1, 8), (4, 3), (6, 3), (6, 5)])
True

>>> manhattan(10, 10, [(1, 8), (4, 3), (6, 3), (6, 5)])
****D*****
****D***P*
*****D****
*****DD***
***P*DDD**
DDDDD***DD
***PDP****
****D*****
****D*****
****D*****

Het schiereiland Manhattan vormt één van de vijf stadsdelen van New York. Dit stadsdeel staat bekend om zijn wolkenkrabbers, brede avenues, het financiële centrum Wall Street en de vele, gele taxi's die er rondrijden. De straten van Manhattan zijn ingedeeld volgens het rechthoekige Commissioners' Plan van 1811. Het gebied wordt doorsneden door avenues (noord-zuid) en streets (oost-west).

Manhattan Commissioner's Plan

Veronderstel een gegeven rechthoekig $s \times a$ rooster dat een deelgebied van Manhattan met $s$ streets en $a$ avenues voorstelt. Op verschillende kruispunten zijn pompstations te vinden waar taxi's kunnen tanken. Wanneer een taxi zonder benzine dreigt te vallen, kan de chauffeur op zijn GPS de coördinaten van het dichtsbijzijnde pompstation aflezen. Er is echter een bug in de software van de GPS geslopen. Als er vanaf een kruispunt meerdere "dichtste" pompstations zijn, dan raakt de GPS het noorden kwijt, waardoor de chauffeur in paniek slaat en een aanrijding veroorzaakt. Dergelijke kruispunten worden daarom ook dode punten genoemd.

Opgave

In Manhattan wordt een kruispunt (verder kortweg punt genoemd) op een rechthoekig $s \times a$ rooster steeds voorgesteld als een tuple $(x, y)$, waarbij $x, y \in \mathbb{N}$, $0 \leq x < s$ en $0 \leq y < a$. Het punt in de linkerbovenhoek van het rooster is dus het punt $(0, 0)$, en het punt in de rechteronderhoek is het punt $(s-1, a-1)$. Dit is ook de voorstelling van punten zoals die in deze opgave gebruikt worden.

In Manhattan wordt de afstand tussen twee kruispunten $(x_1, y_1)$ en $(x_2, y_2)$ berekend als $$|x_1 - x_2| + |y_1 - y_2|\,,$$waarbij $|x|$ de absolute waarde van $x$ voorstelt. Deze afstand wordt immers niet voor niets de Manhattan-afstand (of city block distance) genoemd. Schrijf een functie manhattanAfstand die de Manhattan-afstand tussen twee gegeven kruispunten als resultaat teruggeeft. De coördinaten van de twee punten moeten als argument aan de functie doorgegeven worden.
Gebruik de functie manhattanAfstand om een functie doodpunt te schrijven die een Booleaanse waarde teruggeeft die aangeeft of een gegeven kruispunt een dood punt is of niet. Aan deze functie moeten twee argumenten doorgegeven worden: de coördinaten van het kruispunt waarvoor moet bepaald worden of het al dan niet een dood punt is, en een lijst van punten die de locaties van de pompstations op het $s \times a$ rooster aangeven.
Schrijf een functie manhattan waaraan drie argumenten moeten doorgegeven worden: het aantal streets $s$, het aantal avenues $a$, en een lijst van punten die de locaties van de pompstations op het $s \times a$ rooster aangeven. De functie moet een voorstelling van het rechthoekig rooster uitschrijven, waarbij kruispunten worden aangeduid met een sterretje (*). Kruispunten waarop een pompstation gelegen is moeten echter voorgesteld worden met de letter P, en kruispunten die dode punten zijn moeten voorgesteld worden met de letter D.

Voorbeeld

In het voorbeeld $10\times 10$ rooster dat in onderstaande interactieve Python sessie wordt afgebeeld is $(5,0)$ bijvoorbeeld een dood punt, omdat de twee pompstations die op de vierde avenue gelegen zijn allebei op afstand 4 van het punt $(5,0)$ liggen.

>>> manhattanAfstand((3, 5), (7, 9))
8
>>> manhattanAfstand((12, 5), (3, 16))
20
>>> doodpunt((4, 3), [(1, 8), (4, 3), (6, 3), (6, 5)])
False
>>> doodpunt((7, 4), [(1, 8), (4, 3), (6, 3), (6, 5)])
True
>>> manhattan(10, 10, [(1, 8), (4, 3), (6, 3), (6, 5)])
****D*****
****D***P*
*****D****
*****DD***
***P*DDD**
DDDDD***DD
***PDP****
****D*****
****D*****
****D*****

Submit solution!

Added by:	Peter Dawyndt
Date:	2011-09-01
Time limit:	10s-15s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC
Resource:	None