当前位置：首页 > news >正文

01 矩阵（力扣）多源广度优先搜索 JAVA

news 2025/8/17 9:14:20

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

在这里插入图片描述

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

在这里插入图片描述

输入：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] is either 0 or 1.
mat 中至少有一个 0

解题思路：

1、相邻指的是上下左右四方向

2、与其以1为起点，不如以所有0为起点，这是个不错的逆向思维

3、所有0初始值为0，所有1初始值Integer.MAX_VALUE/2

4、前者值 + 1比后者值小即可更新后者值

代码：

class Solution {public int fx[] = {-1, 1, 0, 0};public int fy[] = {0, 0, -1, 1};//上下左右public int INF = Integer.MAX_VALUE / 2;public int[][] updateMatrix(int[][] mat) {int m = mat.length;int n = mat[0].length;Queue<int[]> qu = new LinkedList<>();for(int i = 0; i < m; i ++)for(int j = 0; j < n; j ++)if(mat[i][j] == 0) {qu.add(new int[] {i, j});}else mat[i][j] = INF;bfs(qu, mat, m, n);return mat;}public void bfs(Queue<int[]> qu, int[][] mat, int m, int n) {while(!qu.isEmpty()) {int xy[] = qu.poll();for(int i = 0;i < 4; i ++) {int fxx = xy[0] + fx[i];int fyy = xy[1] + fy[i];if(fxx >= 0 && fxx < m && fyy >= 0 && fyy < n && mat[xy[0]][xy[1]] + 1 < mat[fxx][fyy]) {mat[fxx][fyy] = mat[xy[0]][xy[1]] + 1;qu.add(new int[]{fxx, fyy});}}}}
}