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;
}
}