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

``````class Solution {
public:
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
int res = 0;
vector<vector<int>> mat(N, vector<int>(N, 1));
for (auto mine : mines) mat[mine[0]][mine[1]] = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
int k = 0;
while (canExpand(mat, N, i, j, k)) ++k;
res = max(res, k);
}
}
return res;
}
bool canExpand(vector<vector<int>>& mat, int N, int x, int y, int k) {
if (x - k < 0 || y - k < 0 || x + k >= N || y + k >= N) return false;
return mat[x - k][y] && mat[x][y + k] && mat[x + k][y] && mat[x][y - k];
}
};
``````

``````1  0  1  0
1  1  1  1
1  0  1  1
``````

``````1  0  1  0
1  2  3  4
1  0  1  2
``````

right数组是当前及其右边连续1的个数，如下所示：

``````1  0  1  0
4  3  2  1
1  0  2  1
``````

up数组是当前及其上边连续1的个数，如下所示：

``````1  0  1  0
2  1  2  1
3  0  3  2
``````

down数组是当前及其下边连续1的个数，如下所示：

``````3  0  3  0
2  1  2  2
1  0  1  1
``````

``````class Solution {
public:
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
int res = 0, cnt = 0;
vector<vector<int>> dp(N, vector<int>(N, 0));
unordered_set<int> s;
for (auto mine : mines) s.insert(mine[0] * N + mine[1]);
for (int j = 0; j < N; ++j) {
cnt = 0;
for (int i = 0; i < N; ++i) { // up
cnt = s.count(i * N + j) ? 0 : cnt + 1;
dp[i][j] = cnt;
}
cnt = 0;
for (int i = N - 1; i >= 0; --i) { // down
cnt = s.count(i * N + j) ? 0 : cnt + 1;
dp[i][j] = min(dp[i][j], cnt);
}
}
for (int i = 0; i < N; ++i) {
cnt = 0;
for (int j = 0; j < N; ++j) { // left
cnt = s.count(i * N + j) ? 0 : cnt + 1;
dp[i][j] = min(dp[i][j], cnt);
}
cnt = 0;
for (int j = N - 1; j >= 0; --j) { // right
cnt = s.count(i * N + j) ? 0 : cnt + 1;
dp[i][j] = min(dp[i][j], cnt);
res = max(res, dp[i][j]);
}
}
return res;
}
};
``````

``````class Solution {
public:
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
int res = 0;
vector<vector<int>> dp(N, vector<int>(N, N));
for (auto mine : mines) dp[mine[0]][mine[1]] = 0;
for (int i = 0; i < N; ++i) {
int l = 0, r = 0, u = 0, d = 0;
for (int j = 0, k = N - 1; j < N; ++j, --k) {
dp[i][j] = min(dp[i][j], l = (dp[i][j] ? l + 1 : 0));
dp[j][i] = min(dp[j][i], u = (dp[j][i] ? u + 1 : 0));
dp[i][k] = min(dp[i][k], r = (dp[i][k] ? r + 1 : 0));
dp[k][i] = min(dp[k][i], d = (dp[k][i] ? d + 1 : 0));
}
}
for (int k = 0; k < N * N; ++k) res = max(res, dp[k / N][k % N]);
return res;
}
};
``````

Cheapest Flights Within K Stops

Minimum Swaps To Make Sequences Increasing

Soup Servings

https://leetcode.com/problems/largest-plus-sign/solution/

https://leetcode.com/problems/largest-plus-sign/discuss/113314/JavaC++Python-O(N2)-solution-using-only-one-grid-matrix

https://leetcode.com/problems/largest-plus-sign/discuss/113350/C++-simple-brute-force-easy-to-understand-with-detailed-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation