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

{% hint style="info" %}
暴力解就是兩層loop然後每個grid往上下左右搜尋，所以time complexity是O(n^3)。
{% endhint %}

```cpp
// Brute Force
bool canExpand(vector<vector<int> >& matrix, int N, int x, int y, int k) {
    if (x - k < 0 || y - k < 0 || x + k >= N || y + k >= N) return false;
    return matrix[x + k][y] && matrix[x - k][y] && matrix[x][y + k] && matrix[x][y - k];
}
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) { // time: O(N^3); space: O(N^2)
    int res = 0;
    vector<vector<int> > matrix(N, vector<int>(N, 1));
    for (auto& mine : mines) matrix[mine[0]][mine[1]] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            int k = 0;
            while (canExpand(matrix, N, i, j, k)) ++k;
            res = max(res, k);
        }
    }
    return res;
}
```

{% hint style="info" %}
利用一個hashset把0的位置存起來，然後一個2D DP table存每個位置能形成的最大＋符號的order是多少。
{% endhint %}

```cpp
// Dynamic programming
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) { // time: O(N^2); space: O(N^2)
    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;
        // Up
        for (int i = 0; i < N; ++i) {
            cnt = s.count(i * N + j) ? 0 : cnt + 1;
            dp[i][j] = cnt;
        }
        cnt = 0;
        // Down
        for (int i = N - 1; i >= 0; --i) {
            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;
        // Left
        for (int j = 0; j < N; ++j) {
            cnt = s.count(i * N + j) ? 0 : cnt + 1;
            dp[i][j] = min(dp[i][j], cnt);
        }
        cnt = 0;
        // Right
        for (int j = N - 1; j >= 0; --j) {
            cnt = s.count(i * N + j) ? 0 : cnt + 1;
            dp[i][j] = min(dp[i][j], cnt);
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            res = max(res, dp[i][j]);
        }
    }
    return res;
}
```

{% hint style="info" %}
其實也不需要hashset輔助，直接初始化dp table為所有都是1，然後把mines的位置設為0，之後scan時，不為0的grid代表不是mine的地方。
{% endhint %}

```cpp
// Dynamic Programming
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) { // time: O(N^2); space: O(N^2)
    int res = 0, cnt = 0;
    vector<vector<int> > dp(N, vector<int>(N, 1));
    for (auto& mine : mines) dp[mine[0]][mine[1]] = 0;
    for (int j = 0; j < N; ++j) {
        cnt = 0;
        // Up
        for (int i = 0; i < N; ++i) {
            if (dp[i][j]) cnt += 1;
            else cnt = 0;
            dp[i][j] = cnt;
        }
        cnt = 0;
        // Down
        for (int i = N - 1; i >= 0; --i) {
            if (dp[i][j]) cnt += 1;
            else cnt = 0;
            dp[i][j] = min(dp[i][j], cnt);
        }
    }
    for (int i = 0; i < N; ++i) {
        cnt = 0;
        // Left
        for (int j = 0; j < N; ++j) {
            if (dp[i][j]) cnt += 1;
            else cnt = 0;
            dp[i][j] = min(dp[i][j], cnt);
        }
        cnt = 0;
        // Right
        for (int j = N - 1; j >= 0; --j) {
            if (dp[i][j]) cnt += 1;
            else cnt = 0;
            dp[i][j] = min(dp[i][j], cnt);
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            res = max(res, dp[i][j]);
        }
    }
    return res;
}
```

{% hint style="info" %}
上述的DP解法經過整理讓code更為簡潔。
{% endhint %}

```cpp
// Dynamic programming
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) { // time: O(N^2); space: O(N^2)
    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 && k >= 0; ++j, --k) {
            dp[i][j] = min(dp[i][j], l = (dp[i][j]) ? l + 1 : 0);
            dp[i][k] = min(dp[i][k], r = (dp[i][k]) ? r + 1 : 0);
            dp[j][i] = min(dp[j][i], u = (dp[j][i]) ? u + 1 : 0);
            dp[k][i] = min(dp[k][i], d = (dp[k][i]) ? d + 1 : 0);
        }
    }
    for (int l = 0; l < N * N; ++l) {
        res = max(res, dp[l / N][l % N]);
    }
    return res;
}
```
