## 矩阵中十字形的最大阶（1组成的十字的最大长度），Largest Plus Sign 原

叶枫啦啦

In a 2D `grid` from (0, 0) to (N-1, N-1), every cell contains a `1`, except those cells in the given list `mines` which are `0`. What is the largest axis-aligned plus sign of `1`s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An "axis-aligned plus sign of `1`s of order k" has some center `grid[x][y] = 1` along with 4 arms of length `k-1` going up, down, left, and right, and made of `1`s. This is demonstrated in the diagrams below. Note that there could be `0`s or `1`s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

Examples of Axis-Aligned Plus Signs of Order k:

```Order 1:
000
010
000
Order 2:
00000
00100
01110
00100
00000
Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000```

Example 1:

```Input: N = 5, mines = [[4, 2]]
Output: 2
Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can only be order 2.  One of them is marked in bold.```

Example 2:

```Input: N = 2, mines = []
Output: 1
Explanation:
There is no plus sign of order 2, but there is of order 1.```

Example 3:

```Input: N = 1, mines = [[0, 0]]
Output: 0
Explanation:
There is no plus sign, so return 0.```

Note:

1. `N` will be an integer in the range `[1, 500]`.
2. `mines` will have length at most `5000`.
3. `mines[i]` will be length 2 and consist of integers in the range `[0, N-1]`.
4. (Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)

【题意】

“k阶十字形全1区域”中心点[x] [y] = 1以及长度为k-1的四向上，向下，向左和向右方向的点，均由1构成。

Input: N = 5, mines = [[4, 2]]

Input: N = 2, mines = []

Input: N = 1, mines = [[0, 0]]

0 因为没有满足十字形全1区域的值，所以返回0.

①  https://leetcode.com/problems/largest-plus-sign/discuss/113314

• 对于每个位置（i，j），我们只关心四个方向中的包含1的最小长度。这意味着我们可以通过只跟踪最小长度来将这四个矩阵组合成一个矩阵。
• 对于每个位置（i，j），当且仅当grid [i] [j] == 0时，以其为中心的十字形全1区域的阶为0.这意味着我们可以进一步将网格矩阵与上面得到的那个合并。

grid[i][j]表示第i行第j列的元素的十字形全1区域的阶。时间复杂度O（n^2），空间复杂度O（n^2）

class Solution { //143ms
public int orderOfLargestPlusSign(int N, int[][] mines) {
int[][] grid = new int[N][N];
for (int i = 0;i < N;i ++){//初始化为矩阵的