01 Matrix

题目

https://leetcode-cn.com/problems/01-matrix/

解

有点难，虽然是中等，可是还是没写出来，最后时间到了，看了题解

package main

import "math"

func updateMatrix(matrix [][]int) [][]int {
    if len(matrix) == 0 {
        return [][]int{}
    }
    if len(matrix[0]) == 0 {
        return [][]int{}
    }
    // 初始化
    var ret = make([][]int, len(matrix))
    for i := 0; i < len(matrix); i++ {
        var t []int
        for j := 0; j < len(matrix[0]); j++ {
            t = append(t, math.MaxInt32)
        }
        ret[i] = t
    }
    for i := 0; i < len(matrix); i++ {
        for j := 0; j < len(matrix[0]); j++ {
            if matrix[i][j] == 0 {
                ret[i][j] = 0
            }
        }
    }
    for i := 0; i < len(matrix); i++ {
        for j := 0; j < len(matrix[0]); j++ {

            if matrix[i][j] == 0 {
                continue
            }
            if i-1 >= 0 {
                ret[i][j] = Min(ret[i][j], ret[i-1][j]+1)
            }
            if j-1 >= 0 {
                ret[i][j] = Min(ret[i][j], ret[i][j-1]+1)
            }
        }
    }
    for i := len(matrix) - 1; i >= 0; i-- {
        for j := len(matrix[0]) - 1; j >= 0; j-- {
            if matrix[i][j] == 0 {
                continue
            }
            if i+1 < len(matrix) {
                ret[i][j] = Min(ret[i][j], ret[i+1][j]+1)
            }
            if j+1 < len(matrix[0]) {
                ret[i][j] = Min(ret[i][j], ret[i][j+1]+1)
            }

        }
    }
    return ret
}
func Min(i, j int) int {
    if i > j {
        return j
    }
    return i
}

先记录下来吧，之后找时间复习