今日题目

01 矩阵

这题目是非常经典的dp题目
刚刚看到题目的第一感觉就是暴力或者广搜。对于每个点，遍历最近的点，然后计算距离。emmm这题目做着做着就想到要是隔离的点都计算好了，那不是可以直接对应那个点的上下左右最小的值+1就是了呢？是的。没错。那这题目就是变成了一道动态规划题目。既然是动态规划题目，那状态转移方程就是解决问题的关键了。刚刚分析的题目过程也就是写状态转移方程的关键了。
具体的状态转移方程是

有了状态转移方程那问题就简单多了，下个问题就是怎么初始状态了。如果直接对矩阵进行计算的话，因为缺少初始状态，所以就错了。我直接开了一个新的二维数组初始化，然后先左和上遍历，再右和下遍历。

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 {
                    //状态转移方程
                    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--) {
                //状态转移方程
                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;
    }