542. 01 矩阵

题目描述

给定一个 0-1矩阵，返回每个点到0的最近距离。

样例

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

题目解析

两遍的动态规划，因为一个点距离最近 0 的距离是由上下左右四个方向判断的。我们可以从左上到右下进行一次动态搜 索，再从右下到左上进行一次动态搜索。两次动态搜索即可完成四个方向上的查找。

代码示例

编程实现上， Go 语言是不能在初始化的时候，使用 math.MaxInt64， 因为math.MaxInt64 + 1 的时候，会变成负无穷大，从而取得错误的结果。因为我们知道最坏的情况是，0 ，1 分别在左上角和右下角，所以最坏的情况是 m + n 次。

func min(a, b int) int {
    if a > b {
        return b
    }
    return a 
}

func updateMatrix(matrix [][]int) [][]int {
    // 初始化数组
    n, m := len(matrix), len(matrix[0])
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, m)
        for j := 0; j < m; j++ {
            if matrix[i][j] == 0 {
                dp[i][j] = 0  
            } else {
                // dp[i][j] = math.MaxInt64 // Go 语言会出错
                dp[i][j] = m + n
            }
        }
    }
   
    // 左上到右下
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if matrix[i][j] == 1 {
                if i > 0 {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
                }
                if j > 0 {
                    dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
                }
            }
        }
    }
    // 右下到左上
    for i := n - 1; i >= 0 ; i-- {
        for j := m - 1; j >= 0; j-- {
            if matrix[i][j] == 1 {
                if i + 1 < n {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1)
                }
                if j + 1 < m {
                    dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1)
                }
            }
        }
    }
    return dp
}