你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋，请返回 -1。
示例 1：
1输入：[[1,0,1],[0,0,0],[1,0,1]] 2输出：2 3解释： 4海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
示例 2：
1输入：[[1,0,0],[0,0,0],[0,0,0]] 2输出：4 3解释： 4海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。
提示：
1 <= grid.length == grid[0].length <= 100grid[i][j]不是0就是1
Solution:
其实这一题跟number of islands很像，都是bfs把0变1的4-way搜索。对于每一个0(water)，都存在离它最近的陆地距离，需要找到所有的距离中的最大值。解法就是把陆地放到deque队列中，再逐层搜索，每一次把d=1,d=2,...递增的所有的0都找到并变为1，逐层distance增加，最后返回的就是最大距离。
1from collections import deque 2 3class Solution(object): 4 def maxDistance(self, grid): 5 """ 6 :type grid: List[List[int]] 7 :rtype: int 8 """ 9 10 lands = deque([]) # python的队列是deque 11 n, res = len(grid), -1 12 for x in range(n): 13 for y in range(n): 14 if grid[x][y]: # land found 15 lands.append((x, y)) 16 17 if len(lands) == 0 or len(lands) == n*n: 18 return res 19 20 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] 21 while lands: 22 num = len(lands) 23 for _ in range(num): 24 x0, y0 = lands.popleft() # tuple还能这样用 25 for i in range(4): # 4-way bfs search 26 x, y = x0 + dx[i], y0 + dy[i] 27 if 0 <= x < n and 0 <= y < n and not grid[x][y]: # water found 28 grid[x][y] = 1 # 很像number of islands 29 lands.append((x, y)) 30 res += 1 31 32 return res