title
你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
如果网格上只有陆地或者海洋，请返回 -1。
示例 1：
输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
示例 2：
输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。
提示：
1 <= grid.length == grid[0].length <= 100grid[i][j]不是0就是1
solution
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
if not grid: return 0
m, n = len(grid), len(grid[0])
q = collections.deque()
dist = [[-1 for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
dist[i][j] = 0
q.append((i, j))
step = 0
dirs = (-1, 0, 1, 0, -1)
while len(q) > 0:
step += 1
for _ in range(len(q)):
r0, c0 = q.popleft()
for k in range(4):
r, c = r0 + dirs[k], c0 + dirs[k + 1]
if 0 <= r < m and 0 <= c < n and dist[r][c] == -1:
dist[r][c] = step
q.append((r, c))
res = max([max(l) for l in dist])
return res if res > 0 else -1