Closest Leukocyte V77935

We represent a petri dish with a cell culture as a matrix, where positions with an ’L’ represent a leukocyte, and positions with a dot represent empty spaces.

For instance:

. . . . . L . .
. . . . . . . .
. . . . L . . L
. . . . . . . .
. . . . . . . .
. . L L . . . .

We want to be able to spot the closest leukocyte to any given position in the culture (so we can know which one would get there sooner if a bacteria were to fall in that position).

Write a function ’closest’ that given the matrix and a list of positions that might potentially contain bacteria, returns a list with the position of the closest leucocyte to each position in the list. If there is a tie, the topmost leftmost one.

def closest(culture, positions)

You can assume there is always at least one leucocyte in the cultive (and thus, that the matrix is not empty).

If you need it, you may use the following function to compute the distance between two positions in the culture:

def distance(x1,y1,x2,y2):
 '''
    Input: coordinates of two positions (x1,y1) (x2,y2) 
    Output: Shortest distance from (x1,y1) to (x2,y2) in number of matrix
            cells (moving either horizontally, vertically or diagonally)
    '''
    return max(abs(x1-x2), abs(y1-y2))

Observation

Hint 1: the matrix is sparse, there are few positions with leukocytes.
Hint 2: the list of positions may be very long.

IMPORTANT: Submit only the function(s). If you have a main program, comment it out or embed it inside a conditional if __name__ == '__main__':