01 矩阵（力扣）多源广度优先搜索 JAVA-Toy模板网

这篇具有很好参考价值的文章主要介绍了01 矩阵（力扣）多源广度优先搜索 JAVA。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

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

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

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

输入：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});
    			}
    				 
    		}
    	}
    }
}