[leetcode] 1162 map analysis

Now you have a copy of n x n Of grid grid, Each of the above Cell Use both 0 and 1 It's marked . among 0 On behalf of the ocean ,1 Representing land .

Please find an ocean cell , The ocean cell has the largest distance to the nearest land cell , And return the distance . If there's only land or ocean on the grid , Please return -1.

The distance we're talking about here is 「 Manhattan distance 」（ Manhattan Distance）：(x0, y0) and (x1, y1) The distance between these two cells is |x0 - x1| + |y0 - y1| .

Example 1：

Input ： grid = [[1,0,1],[0,0,0],[1,0,1]]
Output ： 2
explain ：
Ocean cell (1, 1) And the distance between all the land cells reaches the maximum , The maximum distance is 2.

Example 2：

Input ： grid = [[1,0,0],[0,0,0],[0,0,0]]
Output ： 4
explain ：
Ocean cell (2, 2) And the distance between all the land cells reaches the maximum , The maximum distance is 4.

Tips ：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] No 0 Namely 1

Ideas ：
Breadth first traversal , Start with every piece of land , Assign values to all accessible oceans （ distance ）

# Breadth first traversal 
class Solution(object):
    def maxDistance(self,grid):
        n = len(grid)# Get the size of the sequence 
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:# Meet land , Start breadth traversal and assign values to the ocean （ Distance ）
                    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