成都网站建设公司官网,河源网站建设 科技,站长如何做视频类网站,网站广告位有哪些给定一个由 0 和 1 组成的矩阵 mat #xff0c;请输出一个大小相同的矩阵#xff0c;其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 输入#xff1a;mat [[0,0,0],[0,1,0],[0,0,0]] 输出#xff1a;[[0,0,0],[0,1,0],[0,0,0]] 输入… 给定一个由 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;Queueint[] 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(Queueint[] 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});}}}}
}
