In a certain region, there are a number of hospitals that are situated in a close range from one another. The competition between these hospitals is lethal, and that is to be taken literally. Patients that are transported by ambulance, are not always brought to the nearest hospital. Consequentially, valuable time is lost, sometimes with lethal consequences. The local authorities want to put an end to this, and have put out a new rule that obliges the paramedics to bring their patients to the nearest hospital. In order to do so, a map must be constructed dividing the region in zones with one hospital per zone.

zoneplan euclidisch
Zone map that was constructed for 20 hospitals (situated in locations that were indicated with a black dot), with distances calculated based on the Euclidean distance.
zoneplan manhattan
Zone map that was constructed for 20 hospitals (the locations of which were indicated with a black dot), with distances calculated based on the Manhattan distance.

The authorities are asking you to make a division of a region, so that the nearest hospital on every point of a zone is always the only hospital situated in that zone. The individual hospitals, however, want to keep their sphere of influence as large as possible, and therefore, there is a lot of discussion about the way in which the distance between two points must be calculated. The table below contains a number of possible definitions the hospitals propose in order to calculate the distance between two points $$(x_1, y_1)$$ en $$(x_2, y_2)$$.

name formula
Euclidean distance $$d=\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$$
Manhattan distance $$d=|x_1-x_2| + |y_1-y_2|$$
chessboard distance $$d=\max(|x_1-x_2|,|y_1-y_2|)$$

Assignment

Consider a rectangular region in which a number of hospitals are situated. We have divided this region in square cells that form a grid, so that each cell contains one hospital at the most. The rows and columns of the grid are respectively numbered from tow to bottom and from left to right, starting from 0. The cells of teh grid in which the hospital is situated, is marked with a (unique) uppercase letter and the remainder is marked with a full stop. The positions of the hospital can no be represented by a map of the following format:

......B..
.........
...A.....
.........
.......D.
.........
.C.......
.....E...
.........

The position of a cell in the grid is represented by a tuple $$(r, k)$$. Here, $$r$$ is the row number and $$k$$ is the column number for a cell in the grid. Asked: 

Example

In the example session below, we assume that the file hospitals.txt1 is situated in the current directory.

>>> euclideanDistance((0, 0), (3, 4))
5.0
>>> manhattanDistance((0, 0), (3, 4))
7.0
>>> chessboardDistance((0, 0), (3, 4))
4.0

>>> positions('hospitals.txt')
(9, 9, {(0, 6): 'B', (4, 7): 'D', (7, 5): 'E', (2, 3): 'A', (6, 1): 'C'})

>>> nearest((0, 0), {(0, 6): 'B', (4, 7): 'D', (7, 5): 'E', (2, 3): 'A', (6, 1): 'C'})
'A'
>>> nearest((8, 8), {(0, 6): 'B', (4, 7): 'D', (7, 5): 'E', (2, 3): 'A', (6, 1): 'C'}, distance=manhattanDistance)
'E'

>>> zones('hospitals.txt')
aaaabbBbb
aaaaabbbb
aaaAaabdd
aaaaaaddd
ccaaaddDd
cccceeddd
cCcceeedd
ccceeEeee
ccceeeeee
>>> zones('hospitals.txt', distance=manhattanDistance)
aaaabbBbb
aaaaabbbb
aaaAaabdd
aaaaaaddd
ccaaaddDd
cccaeeddd
cCcceeedd
ccceeEeee
ccceeeeee
>>> zones('hospitals.txt', distance=chessboardDistance)
aaaaabBbb
aaaaabbbb
aaaAaabbb
aaaaaaddd
caaaaadDd
ccccedddd
cCcceeedd
cccceEeed
cccceeeee
>>> zones('hospitals.txt', 'zones.txt')