题目描述

blablabla

样例

blablabla

算法

(DP) $O(n * m)$

用DP遍历两次 ， 第一次从左上角遍历到右下角，dp[i][j] 为 (i,j) 到 当前位置的左上方最近0的距离
转移方程为 ： dp[i][j] == Math.min(dp[i - 1][j], dl[i][j - 1]) + 1;

第二次从右下角遍历到左上角，dp[i][j] 为 (i,j) 到 当前位置的右下方最近0的距离
转移方程为 ： dp[i][j] == Math.min(Math.min(dp[i + 1][j], dl[i][j + 1]) + 1, dp[i][j])

时间复杂度分析：两次遍历都是O(n * m)时间，总时间为O(n * m).

JAVA 代码

class Solution {
    int[][] dirs = {{-1,0,1,0},{0,-1,0,1}};
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return matrix;
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) 
                    dp[i][j] = 0;
                else {
                    int up = i > 0 ? dp[i - 1][j] : n * m;
                    int left = j > 0 ? dp[i][ j - 1] : n * m;
                    dp[i][j] = Math.min(up, left) + 1;
                }
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if (matrix[i][j] == 0) 
                    dp[i][j] = 0;
                else {
                    int down = i < n - 1  ? dp[i + 1][j] : n * m;
                    int right = j < m - 1  ? dp[i][j + 1] : n * m;
                    dp[i][j] = Math.min(Math.min(down, right) + 1, dp[i][j]);
                }
            }
        }
        return dp;
    }

}