地图分析

难度: Medium

你现在手里有一份大小为 n x n 的网格 grid，上面的每个单元格都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

示例 1：

输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

示例 2：

输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释： 
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

提示：

n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] 不是 0 就是 1

Submission

运行时间: 109 ms

内存: 16.8 MB

class Solution:
    from collections import deque
    def maxDistance(self, grid: List[List[int]]) -> int:
        queue = deque()
        n = len(grid)
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    queue.append((i,j))
        
        if len(queue) == 0 or len(queue) == n*n:
            return -1

        dist = -1
        # 从(i,j)开始遍历
        while len(queue) > 0:
            dist += 1
            m = len(queue)
            for i in range(m):
                r, c = queue.popleft()

                if r-1>= 0 and grid[r-1][c] == 0:
                    grid[r-1][c] = 2
                    queue.append((r-1,c))
                
                if r+1<=n-1 and grid[r+1][c] == 0:
                    grid[r+1][c] = 2
                    queue.append((r+1,c))
                
                if c-1>= 0 and grid[r][c-1] == 0:
                    grid[r][c-1] = 2
                    queue.append((r,c-1))
                
                if c+1<=n-1 and grid[r][c+1] == 0:
                    grid[r][c+1] = 2
                    queue.append((r,c+1))
        return dist

Explain

这个题解采用了广度优先搜索（BFS）的方法来解决问题。首先，它遍历整个网格，将所有陆地单元格的位置添加到队列中。接着，从所有陆地单元格开始同步扩展到相邻的海洋单元格，同时记录扩展的层数，这相当于从陆地到海洋单元格的最短距离。每扩展一层，距离就增加1。当不再有海洋单元格可以继续扩展时，最后记录的距离就是最大的海洋单元格到最近陆地单元格的距离。如果初始时队列为空（即没有陆地）或队列大小等于网格的单元格总数（即全是陆地），则直接返回-1。

时间复杂度: O(n*n)

空间复杂度: O(n*n)

class Solution:
    from collections import deque
    def maxDistance(self, grid: List[List[int]]) -> int:
        queue = deque()
        n = len(grid)
        # 将所有陆地单元格添加到队列
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    queue.append((i,j))
        
        # 检查是否全是陆地或全是海洋
        if len(queue) == 0 or len(queue) == n*n:
            return -1

        dist = -1
        # 使用BFS扩展到所有可达的海洋单元格
        while len(queue) > 0:
            dist += 1
            m = len(queue)
            for i in range(m):
                r, c = queue.popleft()

                # 将邻近的海洋单元格加入队列，并标记为已访问（2）
                if r-1>= 0 and grid[r-1][c] == 0:
                    grid[r-1][c] = 2
                    queue.append((r-1,c))
                if r+1<=n-1 and grid[r+1][c] == 0:
                    grid[r+1][c] = 2
                    queue.append((r+1,c))
                if c-1>= 0 and grid[r][c-1] == 0:
                    grid[r][c-1] = 2
                    queue.append((r,c-1))
                if c+1<=n-1 and grid[r][c+1] == 0:
                    grid[r][c+1] = 2
                    queue.append((r,c+1))
        return dist

Explore

在BFS中，标记海洋单元格为2的时机是在这个单元格确定要加入队列时，这样做是为了避免将同一个单元格多次加入队列。如果延迟标记直到单元格从队列中取出，那么在这个单元格被处理之前，相同的海洋单元格可能会被重复发现并多次加入队列，这会导致不必要的重复工作和增加内存消耗。因此，在单元格被加入队列的同时进行标记，是为了优化性能并防止重复处理。

在此BFS实现中，通过将访问过的海洋单元格的值从0改为2来标记这些单元格已经被处理过。这种方式确保了一旦单元格被标记为2，它就不会再次被加入队列或被重新处理。每当扩展到一个新单元格时，算法检查其值是否为0（未访问的海洋单元格），只有满足这个条件的单元格才能被加入队列并在之后被处理。这样，每个单元格最多被处理一次，从而避免了重复处理。

是的，这个处理逻辑能够正确处理所有边缘情况。如果队列初始为空，意味着网格中没有陆地，因此没有起始点来进行BFS，所以返回-1是合理的。同样，如果队列的大小等于网格的单元格总数，意味着网格全是陆地，不存在海洋单元格，因此也应返回-1表示没有海洋单元格可以计算距离。这个逻辑适用于任何大小的网格，无论是极小的网格（如1x1）还是极大的网格。

这是通过在单元格加入队列时立即将其标记为已访问（在本题中标记为2）来保证的。这种立即标记确保了一旦单元格被加入队列，就不会再次被加入。因此，每个单元格在整个BFS过程中只会被入队和出队一次。这不仅避免了重复处理，还提高了算法的效率和执行速度。