leetcode [1162] 地图分析

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

你现在手里有一份大小为 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 <= 100
grid[i][j] 不是 0 就是 1

来自题解:

先把陆地入队列，然后对每个陆地的海洋周边加上距离1，然后对将海洋周边入队列。直到所有的位置都访问过。由于广度优先遍历，因此最后访问到的那个位置，就是距离陆地最远的海洋。

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        # 地图规模
        n, m = len(grid), len(grid[0])
        # 每个点到陆地的曼哈顿距离
        dist = [[10**6 for _ in range(m)] for _ in range(n)]
        # 该点是否被访问过
        visited = [[False for _ in range(m)] for _ in range(n)]
        # 队列
        q = []
        # 陆地计数
        cnt = 0
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j]:
                    dist[i][j] = 0
                    visited[i][j] = True
                    q.append((i, j))
                    cnt += 1
        # 如果都是陆地或者都是海洋，则返回-1
        if cnt == n * m or cnt == 0:
            return -1
        while q:
            x, y = q.pop(0) # 出列
            for i, j in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                # 如果坐标合法并且没被访问过
                if 0 <= i < n and 0 <= j < m and not visited[i][j]:
                    dist[i][j] = min(dist[i][j], dist[x][y] + 1) # 取最小值
                    ans = max(ans, dist[i][j]) # 更新答案
                    visited[i][j] = True
                    q.append((i, j)) # 入列
        return ans

记录所有的岛屿到队列中，搜索邻居，如果没有访问过，那么加入队列然后更新最大距离。

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        if len(grid) == 0 or len(grid[0]) == 0:
            return 0
        
        level = []
        ans = -1
        visited = [[False] * len(grid[0]) for _ in range(len(grid))]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    level.append((i, j, 0))
                    visited[i][j] = True
        while level:
            x, y, dis = level.pop(0)
            for i, j in [
                [x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]
            ]:
                if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and not visited[i][j]:
                    level.append((i, j, dis + 1))
                    visited[i][j] = True
                    ans = max(ans, dis + 1)
        
        return ans