『图；广度优先遍历』地图分析1162

题目相关

• 原题链接：1162. 地图分析 - 力扣（LeetCode）
• 涉及知识：图、广度优先遍历
• 题目难度：★★

题目解读

由于之前没怎么接触过这类题型，所以想到的只是最粗浅的暴力遍历的法子。
看了官方的题解以及其他大神的题解之后，自己收获良多。好一个多源广度优先遍历！
详细解读以及多源广度优先遍历详见：吃鲸🐳！广搜还能多源？看完秒懂! - 地图分析 - 力扣（LeetCode）。
另附一个也挺不错的解析：🌊简单Java, 秒懂图的BFS～ - 地图分析 - 力扣（LeetCode）

Python相关

无

具体实现

这里也是拾人牙慧，主要是照搬上面解析的一个评论中的代码。

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        N = len(grid)
        lands = [(x, y) for x in range(N) for y in range(N) if grid[x][y] ] # 获取所有陆地
        if len(lands) == 0 or len(lands) == N*N:
            return -1
        def valid(x, y): # 判断区域是否合法
            return -1 < x < N and -1 < y < N
        length = -1
        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        # 以下是多源广度优先搜索的实现，具体参见[吃鲸🐳！广搜还能多源？看完秒懂! - 地图分析 - 力扣（LeetCode）](https://leetcode-cn.com/problems/as-far-from-land-as-possible/solution/zhen-liang-yan-sou-huan-neng-duo-yuan-kan-wan-miao/)
        while lands: 
            length += 1
            tmp = set()
            for land in lands:
                for x, y in directions:
                    x_ , y_ = land[0] + x, land[1] + y
                    if valid(x_, y_) and not grid[x_][y_]:
                        grid[x_][y_] = -1 # 表示该海洋区域被访问过
                        tmp.add((x_, y_))
            lands = tmp # 更新待搜索区域
        return length