## 764. 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.)

## Rust Solution

``````struct Solution;

impl Solution {
fn order_of_largest_plus_sign(n: i32, mines: Vec<Vec<i32>>) -> i32 {
let n = n as usize;
let mut grid = vec![vec![1; n]; n];
let mut left = vec![vec![0; n]; n];
let mut top = vec![vec![0; n]; n];
let mut right = vec![vec![0; n]; n];
let mut bottom = vec![vec![0; n]; n];
for mine in mines {
let i = mine[0] as usize;
let j = mine[1] as usize;
grid[i][j] = 0;
}
for i in 0..n {
for j in 0..n {
if grid[i][j] == 1 {
if j > 0 {
left[i][j] = left[i][j - 1] + 1;
} else {
left[i][j] = 1;
}
}
}
}
for j in 0..n {
for i in 0..n {
if grid[i][j] == 1 {
if i > 0 {
top[i][j] = top[i - 1][j] + 1;
} else {
top[i][j] = 1;
}
}
}
}
for i in 0..n {
for j in (0..n).rev() {
if grid[i][j] == 1 {
if j + 1 < n {
right[i][j] = right[i][j + 1] + 1;
} else {
right[i][j] = 1;
}
}
}
}
for j in 0..n {
for i in (0..n).rev() {
if grid[i][j] == 1 {
if i + 1 < n {
bottom[i][j] = bottom[i + 1][j] + 1;
} else {
bottom[i][j] = 1;
}
}
}
}
let mut res = 0;
for i in 0..n {
for j in 0..n {
let mut min = n;
min = min.min(left[i][j]);
min = min.min(right[i][j]);
min = min.min(top[i][j]);
min = min.min(bottom[i][j]);
res = res.max(min);
}
}
res as i32
}
}

#[test]
fn test() {
let n = 5;
let mines = vec_vec_i32![[4, 2]];
let res = 2;
assert_eq!(Solution::order_of_largest_plus_sign(n, mines), res);
let n = 2;
let mines = vec_vec_i32![];
let res = 1;
assert_eq!(Solution::order_of_largest_plus_sign(n, mines), res);
let n = 1;
let mines = vec_vec_i32![[0, 0]];
let res = 0;
assert_eq!(Solution::order_of_largest_plus_sign(n, mines), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.