DP solution in Java


  • 0
    W
       public int[][] updateMatrix(int[][] matrix) {
            int[][] m = new int[matrix.length][matrix[0].length];
            for(int i = 0; i < m.length; ++i)
                for(int j = 0; j < m[0].length; ++j)
                    m[i][j] = Integer.MAX_VALUE;
            update(matrix, m, true, true);
            update(matrix, m, false, false);
            return m;
        }
        private void update(int[][] matrix, int[][] m, boolean incI, boolean incJ) {
            int r = m.length, c = m[0].length, horizontal = 0, vertical = 0;
            for(int i = incI ? 0 : r-1; incI ? i < r : i >= 0; i += incI ? 1 : -1) {
                for(int j = incJ ? 0 : c-1; incJ ? j < c : j >= 0; j += incJ ? 1 : -1) {
                    horizontal = incJ ? j-1 : j+1;
                    vertical = incI ? i-1 : i+1;
                    if(matrix[i][j] == 0) m[i][j] = 0;
                    else {
                        if(horizontal >= 0 && horizontal < c && m[i][horizontal] != Integer.MAX_VALUE && m[i][j] > m[i][horizontal] + 1) m[i][j] = m[i][horizontal] + 1;
                        if(vertical >= 0 && vertical < r && m[vertical][j] != Integer.MAX_VALUE && m[i][j] > m[vertical][j] + 1) m[i][j] = m[vertical][j] + 1;
                    }
                } 
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.