1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」——1162. 地图分析

flypython • • leetcode题解

1162. 地图分析

链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible/
难度：中等

题目

你现在手里有一份大小为 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

思路

这道题就是BFS，我们可以对每个海洋，都向四周扩展，寻找最近的陆地，每次扩展步子+1，最后是找到陆地的步子最大值。

换一种思路，我们拿着陆地找海洋，陆地不断扩展到海洋，每次扩展步子+1，直到所有无法扩展为止。

其实这种思路就是多源BFS，图示如下：

方案代码

解决方案：

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        steps = -1
        queue = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1]
        if len(queue) == 0 or len(queue) == n ** 2: return steps
        while len(queue) > 0:
            for _ in range(len(queue)): 
                x, y = queue.pop(0)
                for xi, yj in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if xi >= 0 and xi < n and yj >= 0 and yj < n and grid[xi][yj] == 0:
                        queue.append((xi, yj))
                        grid[xi][yj] = -1
            steps += 1
                
        return steps

原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/262.html

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 28/03/2020 23:31
下一篇 » 30/03/2020 23:35

相关推荐