764. 最大加号标志.md

764. 最大加号标志

题目传送门

点击这里

解题思路

这道题的方法用的是四个方向的动态规划，分析题意，题意要找的是一个十字型状的全1图形，我们要得出其阶数，可以利用动态规划，找到连续的1的个数，但是四个方向我们可以使用三维dp，也可以用二维处理四次，选择最小值即可。

代码

func orderOfLargestPlusSign(n int, mines [][]int) int {
    var res int
	// 不需要三维的数组，只需要二维的然后向左向右向上向下取同一个位置最小的连续1个数即可
    dp := make([][]int, n) 
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = n
        }
    }
    // 将二维转换成一维，记录好0的位置，这样子做可以让动态规划从三维转换到二维，也节省了一次嵌套for循环
    zero := make(map[int]bool)
    for _, v := range mines {
        zero[v[0]*n+v[1]] = true
    }
    // 向左右遍历
    for i := 0;i < n;i ++ {
        count := 0
        for j := 0;j < n;j ++ {
            // 如果中间出现一次0，那么连续的1的个数就重新置0
            if zero[i*n+j] {
                count = 0
            }else {
                count ++
            }
            dp[i][j] = min(dp[i][j], count)
        }
        count = 0
        for j := n-1;j >= 0;j -- {
            if zero[i*n+j] {
                count = 0
            }else {
                count ++
            }
            dp[i][j] = min(dp[i][j], count)
        }
    }
    // 向上下遍历
    for i := 0;i < n;i ++ {
        count := 0
        for j := 0;j < n;j ++ {
            if zero[i+j*n] {
                count = 0
            }else {
                count ++ 
            }
            dp[j][i] = min(dp[j][i], count)
        }
        count = 0 
        for j := n-1;j >= 0;j -- {
            if zero[i+j*n] {
                count = 0
            } else {
                count ++
            }
            dp[j][i] = min(dp[j][i], count)
            res = max(res, dp[j][i])
        }
    }
    return res
}

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

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