LeetCode LCR 107. 01 矩阵

Categories:

题目描述
思路分析
1. 解法一：多源 BFS（推荐）
相似题目

题目描述

✅ LCR 107. 01 矩阵

思路分析

解法一：多源 BFS（推荐）

核心思路：

把所有 0 的位置作为 BFS 起点，初始距离为 0。

逐层扩展，首次访问到的 1 即为到最近 0 的最短距离。

BFS 结束后得到整张距离矩阵。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 表示矩阵行列。

空间复杂度：O(mn)，队列最坏情况下存所有节点。

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dist = new int[m][n];
        Queue<int[]> queue = new ArrayDeque<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                } else {
                    dist[i][j] = -1;
                }
            }
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];

            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                    continue;
                }

                if (dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        return dist;
    }
}

func updateMatrix(mat [][]int) [][]int {
	m := len(mat)
	n := len(mat[0])
	dist := make([][]int, m)
	queue := make([][2]int, 0)

	for i := 0; i < m; i++ {
		dist[i] = make([]int, n)
		for j := 0; j < n; j++ {
			if mat[i][j] == 0 {
				queue = append(queue, [2]int{i, j})
			} else {
				dist[i][j] = -1
			}
		}
	}

	dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	for head := 0; head < len(queue); head++ {
		r := queue[head][0]
		c := queue[head][1]
		for _, d := range dirs {
			nr := r + d[0]
			nc := c + d[1]
			if nr < 0 || nr >= m || nc < 0 || nc >= n {
				continue
			}
			if dist[nr][nc] == -1 {
				dist[nr][nc] = dist[r][c] + 1
				queue = append(queue, [2]int{nr, nc})
			}
		}
	}

	return dist
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	BFS/DFS
286. 墙与门	中等	多源 BFS
994. 腐烂的橘子	中等	多源 BFS
752. 打开转盘锁	中等	BFS
1091. 二进制矩阵中的最短路径	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/44768078