Laura Bassi was the first female professor at a European university.  
Despite her immense intellect, she was not always allowed to lecture publicly.

One day a professor with very strong beliefs against women in academia sent some `agents` to find Bassi and end her career.

Help her escape by telling her the safest places in town!

Task

```if:python,javascript
Implement the function `advice(agents, n)` where
```
```if:haskell
Implement the function `advice agents n :: [(Int,Int)] -> Int -> [(Int,Int)]` where
```
```if:swift
Implement the function `advice(agents: [[Int]], n: Int) -> [[Int]]` where
```

- `agents` is an array of agent coordinates.
- `n` defines the size of the city that Bassi needs to hide in, in other words the side length of the square grid. 

The function should return a list of coordinates that are the furthest away (by Manhattan distance) from all agents.

As an example, say you have a 6x6 map, and agents at locations

```python
[(0, 0), (1, 5), (5, 1)]
```

The distances to the nearest agent look like this.



The safest spaces are the ones with distance `4`, marked in bright red. So the function should return

```python
[(2, 2), (3, 3), (4, 4), (5, 5)]
```

in any order.

Edge cases:
- If there is an agent on every grid cell, there is no safe space, so return an empty list.
- If there are no agents, then every cell is a safe spaces, so return all coordinates.
- if `n` is `0`, return an empty list.
- If agent coordinates are outside of the map, they are simply not considered.
- There are no duplicate agents on the same square.

Performance

All reference solutions run in around 6 seconds.
You might not pass the tests if you use a brute-force solution.

```if-not:swift,javascript
There are `200` random tests with `n <= 50`. Inefficient solutions might time out.
```
```if:javascript
There are `300` random tests with `n <= 70`. Inefficient solutions might time out.
```
```if:swift
There are `200` random tests with `n <= 70`. Inefficient solutions might time out.
```

This kata is inspired by ThoughtWorks' coding challenge

Difficulty: introductory

Starter code:

def advice(agents, n):
	

Solutions:
def advice(agents, n):
    frontier = { (x,y) for x,y in agents if 0<=x<n and 0<=y<n }
    bag = { (x,y) for x in range(n) for y in range(n)}
    if frontier==bag: return []
    while frontier and bag>frontier:
        bag -= frontier
        frontier = {pos for x,y in frontier for pos in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)) if pos in bag }
    return sorted(bag)

def advice(agents, n):
    agents = [(a[0], a[1]) for a in agents if 0 <= a[0] < n and 0 <= a[1] < n]
    if len(agents) == n * n or n == 0: return []
    grid = [[0] * n for _ in range(n)]
    for ax, ay in agents: grid[ax][ay] = 1
    for ax, ay in agents:
        for dx, dy in [ [1, 0], [0, 1], [-1, 0], [0, -1] ]:
            nx, ny = ax + dx, ay + dy
            if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
                grid[nx][ny] = grid[ax][ay] + 1
                agents.append((nx, ny))
    max_dist = max(d for row in grid for d in row)
    return [(x, y) for x in range(n) for y in range(n) if grid[x][y] == max_dist]

import numpy as np
from scipy import ndimage

def advice(agents, n):
    town = np.ones((n, n)) if n else np.zeros((1, 1))
    for x, y in agents:
        if x < n and y < n:
            town[x, y] = 0
    d = ndimage.distance_transform_cdt(town, metric='taxicab')
    return list(zip(*np.where(d == d.max()))) if d.max() else []

def advice(agents, n):
    # Remove agents outside of bounds
    agents = [(r, c) for r, c in agents if 0 <= r < n and 0 <= c < n]
    
    # Check for degenerate cases, no agents, or all positions filled
    if n == 0 or len(set(agents)) == n * n:
        return []
    
    # Place the agents in the field
    field = [[0 for _ in range(n)] for _ in range(n)]
    edges = []
    for r, c in agents:
        field[r][c] = 1
        edges.append((r, c))
    
    # Flood fill the field in cardinal directions from each edge location that is unfilled
    # Initial edge locations are the positions of the agents
    # Default is all locations if we have no agents
    previous_edges = [(r, c) for r in range(n) for c in range(n)]
    while edges:
        new_edges = []
        for r, c in edges:
            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                rr, cc = r + dr, c + dc
                if 0 <= rr < n and 0 <= cc < n and field[rr][cc] == 0:
                    field[rr][cc] = 1
                    new_edges.append((rr, cc))
        previous_edges, edges = edges, new_edges
    
    # Return the last round of unfilled positions
    return previous_edges


from itertools import starmap, product, count

def _complex_to_point(c):
    return int(c.real), int(c.imag)
    
def _neighbors(point):
    return (point + (1j ** i) for i in range(4))

def advice(agents, n):
    if not n:
        return []
    city = {complex(i, j): None for i, j in product(list(range(n)), repeat=2)}
    last = set(agent for agent in starmap(complex, agents) if agent in city)
    if not last:
        return sorted(_complex_to_point(cell) for cell in city)
    for dist in count():
        city.update({cell: dist for cell in last})
        next_cells = set(
            neighbor for cell in last for neighbor in _neighbors(cell) 
            if neighbor in city and city[neighbor] is None
        )
        if not next_cells:
            return [] if not dist else sorted(_complex_to_point(cell) for cell in last)
        last = next_cells
        
            
            


from collections import deque

INF = 1000000

class Field:
    def __init__(self, n, agents):
        self.n = n
        self.agents = agents
        self.table = [[INF] * n for _ in range(n)]
        self._queue = deque()
        self._calculate_safety()
    
    def _calculate_safety(self):
        for i, j in self.agents:
            if 0 <= i < self.n and 0 <= j < self.n:
                self._add_to_queue(i, j, 0)
        self._process_queue()
                
    def _add_to_queue(self, i, j, value):
        self._queue.append((i, j, value))
        
    def _process_queue(self):
        while self._queue:
            i, j, value = self._queue.popleft()
            if self.table[i][j] != INF:
                continue
            self.table[i][j] = value

            if i < self.n - 1:
                self._add_to_queue(i + 1, j, value + 1)
                
            if i > 0:
                self._add_to_queue(i - 1, j, value + 1)
                
            if j < self.n - 1:
                self._add_to_queue(i, j + 1, value + 1)
                
            if j > 0:
                self._add_to_queue(i, j - 1, value + 1)
      
    @property
    def safest_places(self):
        locations = []
        max_el = 1
        for i in range(self.n):
            for j in range(self.n):
                if self.table[i][j] > max_el:
                    max_el = self.table[i][j]
                    locations = [(i, j)]
                elif self.table[i][j] == max_el:
                    locations.append((i, j))
        return locations
    

def advice(agents, n):
    field = Field(n, agents)
    return field.safest_places

def advice(agents, n):
    agents = { (x,y) for x,y in agents if 0<=x<n and 0<=y<n }
    town = { (x,y) for x in range(n) for y in range(n)}
    if agents==town: return []
    while agents and town>agents:
        town -= agents
        agents = {pos for x,y in agents for pos in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)) if pos in town }
    return sorted(town)

def advice(agents, n):
    if n <= 0:
        return []
    city = [[-1] * n for _ in range(n)]
    agents = [(i, j) for (i, j) in agents if i >= 0 and j >= 0 and i < n and j < n]
    d = 0
    while agents:
        t = []
        for i, j in agents:
            city[i][j] = d
        d += 1
        for i, j in agents:
            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                x, y = i + di, j + dj
                if x < 0 or y < 0 or x >= n or y >= n or city[x][y] >= 0:
                    continue
                city[x][y] = d
                t.append((x, y))
        agents = t
    m = max(max(r) for r in city)
    return [(i, j) for i in range(n) for j in range(n) if city[i][j] == m] if m != 0 else []

def advice(agents, n):
  A = {(i, j) for i, j in agents if 0<=i<n and 0<=j<n}
  B = {(i, j) for i in range(n) for j in range(n)}
  
  if A == B:
    return([])
  
  while len(A) > 0 and A != B:
    B = B - A
    A = {(i, j) for i, j in B 
        if (i+1, j) in A or
           (i-1, j) in A or
           (i, j+1) in A or
           (i, j-1) in A}
    
  return(sorted(list(B)))