542. 01 Matrix

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.The distance between two adjacent cells is 1.Example 1: Input:0 0 00 1 00 0 0Output:0 0 00 1 00 0 0Example 2: Input:0 0 00 1 01 1 1Output:0 0 00 1 01 2 1Note:The number of elements of the given matrix will not exceed 10,000.There are at least one 0 in the given matrix.The cells are adjacent in only four directions: up, down, left and right.难度：medium题目：给定由0､1组成的矩阵，算出每个元素离0最近的距离。相离的两个单元格距离为1.注意：给出的矩阵元素不超过10,000.矩阵至少包含一个0.毗邻的定义为上下左右4个方向。思路：从左上到右下遍历计算一遍，然后再自右下到左上遍历计算一遍。Runtime: 19 ms, faster than 64.23% of Java online submissions for 01 Matrix.public class Solution { public int[][] updateMatrix(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; int maxDis = m * n; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] > 0) { int upDis = (0 == i) ? maxDis : matrix[i - 1][j] + 1; int leftDis = (0 == j) ? maxDis : matrix[i][j - 1] + 1; matrix[i][j] = Math.min(upDis, leftDis); } } } for (int i = m - 1; i >= 0; i–) { for (int j = n - 1; j >= 0; j–) { if (matrix[i][j] > 0) { int downDis = (m - 1 == i) ? maxDis : matrix[i + 1][j] + 1; int rightDis = (n - 1 == j) ? maxDis : matrix[i][j + 1] + 1; matrix[i][j] = Math.min(matrix[i][j], Math.min(downDis, rightDis)); } } } return matrix; }}