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

解题思路

这道题的关键思路是"反向思考"：与其从每个水域开始寻找最近的陆地，不如从所有陆地同时开始向外扩散，找到最远的水域。

核心思想：多源BFS

  1. 初始化：将所有陆地格子（值为1）加入队列作为起点，将所有水域格子标记为未访问
  2. 层次遍历：使用BFS从所有陆地同时向外扩散，每一层代表距离+1
  3. 更新距离：遇到水域格子时，更新其到最近陆地的距离
  4. 记录最大值：在扩散过程中记录遇到的最大距离

算法流程：

  • 首先检查边界情况：如果全是陆地或全是水域，返回-1
  • 将所有陆地坐标入队，距离设为0
  • BFS扩散：每次取出一个格子，向四个方向扩展
  • 遇到未访问的水域时，更新其距离并加入队列
  • 最后一个被访问到的水域距离就是答案

这种方法比为每个水域单独求最近陆地距离更高效，避免了重复计算。

代码实现

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<pair<int, int>> que;
        
        // 将所有陆地加入队列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    que.push({i, j});
                }
            }
        }
        
        // 边界情况：全是陆地或全是海洋
        if (que.empty() || que.size() == n * n) {
            return -1;
        }
        
        int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int maxDist = 0;
        
        // BFS扩散
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                auto [x, y] = que.front();
                que.pop();
                
                for (int d = 0; d < 4; d++) {
                    int nx = x + directions[d][0];
                    int ny = y + directions[d][1];
                    
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                        grid[nx][ny] = grid[x][y] + 1;
                        maxDist = grid[nx][ny] - 1;
                        que.push({nx, ny});
                    }
                }
            }
        }
        
        return maxDist;
    }
};

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        queue = deque()
        
        # 将所有陆地加入队列
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    queue.append((i, j))
        
        # 边界情况：全是陆地或全是海洋
        if not queue or len(queue) == n * n:
            return -1
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        max_dist = 0
        
        # BFS扩散
        while queue:
            x, y = queue.popleft()
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
                    grid[nx][ny] = grid[x][y] + 1
                    max_dist = grid[nx][ny] - 1
                    queue.append((nx, ny))
        
        return max_dist

public class Solution {
    public int MaxDistance(int[][] grid) {
        int n = grid.Length;
        Queue<(int, int)> queue = new Queue<(int, int)>();
        
        // 将所有陆地加入队列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.Enqueue((i, j));
                }
            }
        }
        
        // 边界情况：全是陆地或全是海洋
        if (queue.Count == 0 || queue.Count == n * n) {
            return -1;
        }
        
        int[,] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int maxDist = 0;
        
        // BFS扩散
        while (queue.Count > 0) {
            var (x, y) = queue.Dequeue();
            
            for (int d = 0; d < 4; d++) {
                int nx = x + directions[d, 0];
                int ny = y + directions[d, 1];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    grid[nx][ny] = grid[x][y] + 1;
                    maxDist = grid[nx][ny] - 1;
                    queue.Enqueue((nx, ny));
                }
            }
        }
        
        return maxDist;
    }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
    const n = grid.length;
    const queue = [];
    
    // Find all land cells and add to queue
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                queue.push([i, j]);
            }
        }
    }
    
    // If no land or all land, return -1
    if (queue.length === 0 || queue.length === n * n) {
        return -1;
    }
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let maxDist = 0;
    
    // BFS from all land cells
    while (queue.length > 0) {
        const size = queue.length;
        
        for (let i = 0; i < size; i++) {
            const [row, col] = queue.shift();
            
            for (const [dr, dc] of directions) {
                const newRow = row + dr;
                const newCol = col + dc;
                
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] === 0) {
                    grid[newRow][newCol] = 1;
                    queue.push([newRow, newCol]);
                }
            }
        }
        
        if (queue.length > 0) {
            maxDist++;
        }
    }
    
    return maxDist;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) - 每个格子最多被访问一次
空间复杂度O(n²) - 队列最多存储所有格子

相关题目