题目：

你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋，请返回 -1。
示例 1：

1

输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
示例 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

题目的理解：

计算每一个0到所有1的距离，然后求最小的值，保存到数组A中。然后求A中的最大值，就是需要求得结果。

from typing import List

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        one_list = list()
        zero_list = list()
        length = len(grid)
        for i in range(length):
            for j in range(length):
                if 1 == grid[i][j]:
                    one_list.append((i, j))
                else:
                    zero_list.append((i, j))

        if len(one_list) == 0 or len(zero_list) == 0:
            return -1

        result = list()
        for i, j in zero_list:
            r = map(lambda x: abs(x[0] - i) + abs(x[1] - j), one_list)
            result.append(min(list(r)))

        return max(result)

按这个方法计算的时间复杂度为O(2N*N)，计算超时了。

参考了题解后，使用动态规则进行计算，即从左上开始计算每一个海水到陆地的最短距离，然后从右下角开始计算每一个海水到陆地的最短距离，最后获得最大的值。

python实现

from typing import List

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        length = len(grid)
        counts = [[0] * length for _ in range(length)]
        

        for i in range(length):
            for j in range(length):
                if 1 == grid[i][j]:
                    counts[i][j] = 0
                else:
                    if i - 1 >= 0 and j - 1 >= 0:
                        counts[i][j] = min(counts[i - 1][j], counts[i][j - 1]) + 1
                    elif i - 1 >= 0:
                        counts[i][j] = counts[i - 1][j] + 1
                    elif j - 1 >= 0:
                        counts[i][j] = counts[i][j - 1] + 1
                    else:
                        counts[i][j] = 2 * length

        reverse_range = list(range(length))[::-1]
        for i in reverse_range:
            for j in reverse_range:
                if 1 == grid[i][j]:
                    counts[i][j] = 0
                else:
                    if i + 1 < length and j + 1 < length:
                        counts[i][j] = min(counts[i + 1][j] + 1, counts[i][j + 1] + 1, counts[i][j])
                    elif i + 1 < length:
                        counts[i][j] = min(counts[i + 1][j] + 1, counts[i][j])
                    elif j + 1 < length:
                        counts[i][j] = min(counts[i][j + 1] + 1, counts[i][j])
                    else:
                        counts[i][j] = counts[i][j]

        max_value = 0

        for item in counts:
            max_value = max(max_value, max(item))

        return max_value if max_value != 0 and max_value < 2 * length else -1

这样的计算的时间复杂度O(2NN + N*N), 计算没有超时，成功了。

想看最优解法移步此处

提交

ok

// END 这天气好冷啊，2020年是注定不平凡的一年啊