今日題目

01 矩陣

這題目是非常經(jīng)典的dp題目
剛剛看到題目的第一感覺就是暴力或者廣搜。對于每個點谴仙，遍歷最近的點迂求，然后計算距離。emmm這題目做著做著就想到要是隔離的點都計算好了晃跺，那不是可以直接對應(yīng)那個點的上下左右最小的值+1就是了呢揩局？是的。沒錯掀虎。那這題目就是變成了一道動態(tài)規(guī)劃題目凌盯。既然是動態(tài)規(guī)劃題目，那狀態(tài)轉(zhuǎn)移方程就是解決問題的關(guān)鍵了涩盾。剛剛分析的題目過程也就是寫狀態(tài)轉(zhuǎn)移方程的關(guān)鍵了十气。
具體的狀態(tài)轉(zhuǎn)移方程是

有了狀態(tài)轉(zhuǎn)移方程那問題就簡單多了，下個問題就是怎么初始狀態(tài)了春霍。如果直接對矩陣進行計算的話，因為缺少初始狀態(tài)叶眉，所以就錯了址儒。我直接開了一個新的二維數(shù)組初始化，然后先左和上遍歷衅疙，再右和下遍歷莲趣。

public int[][] updateMatrix(int[][] matrix) {
        /**
         *
         * 功能描述:給定一個由 0 和 1 組成的矩陣，找出每個元素到最近的 0 的距離饱溢。
         *
         * 兩個相鄰元素間的距離為 1 喧伞。
         *
         * @param: [matrix]
         * @return: int[][]
         * @auther: smallfish
         * @date: 2020-03-19 12:16
         */
        if (matrix.length == 0) {
            return matrix;
        }
        int width = matrix.length;
        int length = matrix[0].length;
        int[][] result = new int[width][length];
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < length; j++) {
                //初始化為最大值 （-1的原因是因為后面有計算會+1） 因為這個問題錯了一次。绩郎。潘鲫。。
                result[i][j] = Integer.MAX_VALUE - 1;
            }
        }
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < length; j++) {
                if (matrix[i][j] == 0) {
                    //如果本身為0 則距離為0
                    result[i][j] = 0;
                } else {
                    //狀態(tài)轉(zhuǎn)移方程
                    if (i > 0) {
                        result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
                    }
                    if (j > 0) {
                        result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
                    }
                }
            }
        }

        for (int i = width - 1; i >= 0; i--) {
            for (int j = length - 1; j >= 0; j--) {
                //狀態(tài)轉(zhuǎn)移方程
                if (i < width - 1) {
                    result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
                }
                if (j < length - 1) {
                    result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
                }
            }
        }

        return result;
    }