Medium

题目描述

给定一个由 0 和 1 组成的矩阵 mat，返回每个单元格到最近的 0 的距离。

两个相邻的单元格之间的距离为 1。

示例 1:

输入: mat = [[0,0,0],[0,1,0],[0,0,0]]
输出: [[0,0,0],[0,1,0],[0,0,0]]

示例 2:

输入: mat = [[0,0,0],[0,1,0],[1,1,1]]
输出: [[0,0,0],[0,1,0],[1,2,1]]

提示:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 10^4
  • 1 <= m * n <= 10^4
  • mat[i][j] 不是 0 就是 1
  • mat 中至少有一个 0

解题思路

这是一个典型的多源最短路径问题，可以使用多种方法求解：

方法一：多源BFS（推荐）

  • 将所有为 0 的位置作为起始点同时加入队列
  • 从这些起始点同时向外扩散，第一次到达某个位置时的距离就是最短距离
  • 时间复杂度低，代码简洁

方法二：动态规划

  • 两次遍历：先从左上到右下，再从右下到左上
  • 第一次遍历处理来自上方和左方的最短距离
  • 第二次遍历处理来自下方和右方的最短距离

方法三：单源BFS

  • 对每个为 1 的位置，单独进行 BFS 寻找最近的 0
  • 效率较低，不推荐

多源BFS是最优解法，因为它能够在一次遍历中同时计算所有位置的最短距离，避免了重复计算。算法的核心思想是反向思考：不是从每个 1 去找最近的 0，而是从所有的 0 同时出发去更新周围的距离。

代码实现

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        queue<pair<int, int>> q;
        
        // 将所有0的位置加入队列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        
        vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            
            for (auto& dir : directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && 
                    dist[nx][ny] > dist[x][y] + 1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
        
        return dist;
    }
};

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        dist = [[float('inf')] * n for _ in range(m)]
        queue = []
        
        # 将所有0的位置加入队列
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    dist[i][j] = 0
                    queue.append((i, j))
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while queue:
            x, y = queue.pop(0)
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append((nx, ny))
        
        return dist

public class Solution {
    public int[][] UpdateMatrix(int[][] mat) {
        int m = mat.Length, n = mat[0].Length;
        int[][] dist = new int[m][];
        for (int i = 0; i < m; i++) {
            dist[i] = new int[n];
            Array.Fill(dist[i], int.MaxValue);
        }
        
        Queue<(int, int)> queue = new Queue<(int, int)>();
        
        // 将所有0的位置加入队列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    queue.Enqueue((i, j));
                }
            }
        }
        
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (queue.Count > 0) {
            var (x, y) = queue.Dequeue();
            
            foreach (var dir in directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && 
                    dist[nx][ny] > dist[x][y] + 1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    queue.Enqueue((nx, ny));
                }
            }
        }
        
        return dist;
    }
}

var updateMatrix = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    const result = Array(m).fill().map(() => Array(n).fill(Infinity));
    const queue = [];
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (mat[i][j] === 0) {
                result[i][j] = 0;
                queue.push([i, j]);
            }
        }
    }
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    while (queue.length > 0) {
        const [row, col] = queue.shift();
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                if (result[newRow][newCol] > result[row][col] + 1) {
                    result[newRow][newCol] = result[row][col] + 1;
                    queue.push([newRow, newCol]);
                }
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
多源BFSO(m×n)O(m×n)
动态规划O(m×n)O(1)

说明：

  • 时间复杂度： 每个位置最多被访问一次，总共有 m×n 个位置
  • 空间复杂度： 需要额外的距离矩阵和队列空间，队列最大长度为 O(m×n)

相关题目