01 Matrix-LeetCode#542

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 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2: 
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

思路：从matrix[0][0]开始判断，新建一个整型矩阵res[i][j]

• 如果matrix[i][j] == 0，res[i][j] = 0
• 如果matrix[i][j] == 1， res[i][j]去比较左边（res[i][j – 1]）与上边（res[i – 1][j]），取最小值。

还需要从matrix[matrix.length – 1][matrix[0].length – 1]开始，比较右边（res[i][j + 1]）与下边（res[i + 1][j]）取最小值，再与自身比较取最小值，就是距离最近0的距离。
代码如下：

public class ZeroOneMatrix {
    public int[][] updateMatrix(int[][] matrix) {
        int[][] res = new int[matrix.length][matrix[0].length];
        int x = matrix[0].length;
        int y = matrix.length;
        int max = matrix.length * matrix[0].length;
        for (int i = 0; i < y; i++) {
            for (int j = 0; j < x; j++) {
                if (matrix[i][j] == 0) {
                    res[i][j] = 0;
                } else {
                    int topCell = i > 0 ? res[i - 1][j] : max;
                    int leftCell = j > 0 ? res[i][j - 1] : max;
                    res[i][j] = Math.min(topCell, leftCell) + 1;
                }
            }
        }
        for (int i = y - 1; i >= 0; i--) {
            for (int j = x - 1; j >= 0; j--) {
                if (res[i][j] != 0) {
                    int downCell = i < y - 1 ? res[i + 1][j] : max;
                    int rightCell = j < x - 1 ? res[i][j + 1] : max;
                    res[i][j] = Math.min(Math.min(downCell, rightCell) + 1, res[i][j]);
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        ZeroOneMatrix zeroOneMatrix = new ZeroOneMatrix();
        int[][] matrix = {{0}, {0}, {0}, {0}, {0}};
        zeroOneMatrix.updateMatrix(matrix);
    }
}