难度：★★★☆☆
类型：二维数组
方法：动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中，除了在 mines 中给出的单元为 0，其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶？返回加号标志的阶数。如果未找到加号标志，则返回 0。

一个 k" 阶由 1 组成的“轴对称”加号标志具有中心网格 grid[x][y] = 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。下面给出 k" 阶“轴对称”加号标志的示例。注意，只有加号标志的所有网格要求为 1，别的网格可能为 0 也可能为 1。

k 阶轴对称加号标志示例:

阶 1:
000
010
000

阶 2:
00000
00100
01110
00100
00000

阶 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000

示例 1：

输入: N = 5, mines = [[4, 2]]
输出: 2
解释:

11111
11111
11111
11111
11011

在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。

示例 2：

输入: N = 2, mines = []
输出: 1
解释:

11
11

没有 2 阶加号标志，有 1 阶加号标志。

示例 3：

输入: N = 1, mines = [[0, 0]]
输出: 0
解释:

0

没有加号标志，返回 0 。

提示：

整数N 的范围： [1, 500].
mines 的最大长度为 5000.
mines[i] 是长度为2的由2个 [0, N-1] 中的数组成.
(另外,使用 C, C++, 或者 C# 编程将以稍小的时间限制进行​​判断.)

解答

我们使用动态规划来解决这个问题。

我们需要寻找到方格里最大的加号符号，一个加号符号的定义在题目中已经描述的比较清晰了，一个加号由四个臂组成，需要注意的是四个臂需要等长。如果我们将问题分解为四个子问题，即每个点在四个方向上可以最长延续多长的臂，然后求取四个方向的最小值即可获得以各个点为中心可以获得的加号的尺寸。

我们通过输入构建出网格grid，维度是N×N。

【数组定义】
我们定义一个三维的数组dp，维度为4×(N+2)×(N+2)，三个维度分别表示四个维度，迭代网格高和网格高和宽，并初始化为零，这里需要注意的是，我们相当于将原始网格的周边安排了一圈零元素，是为了动态规划迭代过程的方便和避免越界，因此与dp[*]与grid矩阵的下标之间存在相差1的关系。
dp[0][i+1][j+1]表示grid[i][j]及其正上方的连续1的个数；
dp[1][i+1][j+1]表示grid[i][j]及其正左侧的连续1的个数；
dp[2][i+1][j+1]表示grid[i][j]及其正下方的连续1的个数；
dp[3][i+1][j+1]表示grid[i][j]及其正右侧的连续1的个数。

【递推公式】
为了获得四个方向的计算结果，我们需要进行正向和反向两次遍历：
正向遍历，逐行逐列遍历grid中的元素，如果遇到grid[i-1][j-1]=1，则更新该点对应的dp[0]和dp[1]：
dp[0][i][j] = dp[0][i-1][j]+1 # upper
dp[1][i][j] = dp[1][i][j-1]+1 # left
同理，反向遍历，如果遇到grid[i-1][j-1]=1，则更新该点对应的dp[2]和dp[3]
dp[2][i][j] = dp[2][i+1][j]+1 # lower
dp[3][i][j] = dp[3][i][j+1]+1 # right
最后我们需要返回的是dp中四张图对应位置的最小值组成新图，该图中的每个点就可以代表以该点为中心的最大加号的尺寸，求出整张图中最大值即可。

class Solution:
    def orderOfLargestPlusSign(self, N: int, mines):
        grid = [[1 for _ in range(N)] for _ in range(N)]
        for loc in mines:
            grid[loc[0]][loc[1]] = 0

        dp = [[[0 for _ in range(N+2)] for _ in range(N+2)] for d in range(4)]

        for i in range(1, N+1):
            for j in range(1, N+1):
                if grid[i-1][j-1]:
                    dp[0][i][j] = dp[0][i-1][j]+1       # upper
                    dp[1][i][j] = dp[1][i][j-1]+1       # left
        for i in reversed(range(1, N+1)):
            for j in reversed(range(1, N+1)):
                if grid[i-1][j-1]:
                    dp[2][i][j] = dp[2][i+1][j]+1       # lower
                    dp[3][i][j] = dp[3][i][j+1]+1       # right
        # print(dp)

        result = max([min(dp[d][i][j] for d in range(4)) for j in range(1, N+1) for i in range(1, N+1)])
        return result

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析