【LeetCode】1162-地图分析

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

示例 1：

输入： grid = [[1,0,1],[0,0,0],[1,0,1]]
输出： 2
解释：
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

示例 2：

输入： grid = [[1,0,0],[0,0,0],[0,0,0]]
输出： 4
解释：
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] 不是 0 就是 1

思路：
广度优先遍历，从每一块陆地开始，给所有的能到达的海洋赋值（距离）

#广度优先遍历
class Solution(object):
    def maxDistance(self,grid):
        n = len(grid)#获取数列大小
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:#遇见陆地，开始广度遍历给海洋赋值（即距离）
                    queue = []
                    queue.append((i,j))
                    while queue:
                        x,y = queue[0]
                        tmp = grid[x][y]+1
                        queue.pop(0)
                        for xx,yy in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
                            if 0<=xx<n and 0<=yy<n and (grid[xx][yy]==0 or grid[xx][yy]>tmp):
                                grid[xx][yy] = tmp
                                queue.append((xx,yy))
        result = 0
        for k in grid:
            result = max(result,max(k))
        return result-1 if result!=1 and result!=0 else -1