<p>You are given an integer <code>n</code>. You have an <code>n x n</code> binary grid <code>grid</code> with all values initially <code>1</code>&#39;s except for some indices given in the array <code>mines</code>. The <code>i<sup>th</sup></code> element of the array <code>mines</code> is defined as <code>mines[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> where <code>grid[x<sub>i</sub>][y<sub>i</sub>] == 0</code>.</p>

<p>Return <em>the order of the largest <strong>axis-aligned</strong> plus sign of </em>1<em>&#39;s contained in </em><code>grid</code>. If there is none, return <code>0</code>.</p>

<p>An <strong>axis-aligned plus sign</strong> of <code>1</code>&#39;s of order <code>k</code> has some center <code>grid[r][c] == 1</code> along with four arms of length <code>k - 1</code> going up, down, left, and right, and made of <code>1</code>&#39;s. Note that there could be <code>0</code>&#39;s or <code>1</code>&#39;s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for <code>1</code>&#39;s.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/13/plus1-grid.jpg" style="width: 404px; height: 405px;" />
<pre>
<strong>Input:</strong> n = 5, mines = [[4,2]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> In the above grid, the largest plus sign can only be of order 2. One of them is shown.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/13/plus2-grid.jpg" style="width: 84px; height: 85px;" />
<pre>
<strong>Input:</strong> n = 1, mines = [[0,0]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no plus sign, so return 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>1 &lt;= mines.length &lt;= 5000</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt; n</code></li>
	<li>All the pairs <code>(x<sub>i</sub>, y<sub>i</sub>)</code> are <strong>unique</strong>.</li>
</ul>

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        if (mines.size() == n * n)
            return 0;

        int vecrtical[n][n], horizontal[n][n];
        memset(vecrtical, 1, sizeof vecrtical);

        for (auto& mine : mines)
            vecrtical[mine[0]][mine[1]] = 0;

        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (vecrtical[row][col]) {
                    horizontal[row][col] = 1 + (col == 0 ? 0 : horizontal[row][col-1]);
                    vecrtical[row][col] = 1 + (row == 0 ? 0 : vecrtical[row-1][col]);
                } else horizontal[row][col] = 0;
            }
        }

        int result = 0;
        for (int row = n-1; row >= 0; row--) {
            for (int col = n-1; col >= 0; col--) {
                int maxSize = min(n - 1 - col, (vecrtical[row][col] - 1) / 2);
                for (int len = maxSize; len > 0 && result < len; len--) {
                    if (horizontal[row-len][col+len] > len * 2)
                        result = len;
                }
            }
        }

        return result+1;
    }

    /*int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        vector<vector<bool>> isMine(n, vector<bool>(n));
        for (auto& mine : mines)
            isMine[mine[0]][mine[1]] = true;

        int result = 0;
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                int length = INT_MAX;
                for (int direction = 0; direction < 4; direction++)
                    length = min(length, armLength(isMine, row, col, direction));
                result = max(result, length);
            }
        }

        return result;
    }

    int dp[500][500][4] = {0};
    int directions[5] = { 0, 1, 0, -1, 0 };
    int armLength(vector<vector<bool>>& isMine, int row, int col, int direction) {
        if (row < 0 || row == isMine.size() || col < 0 || col == isMine.size() || isMine[row][col])
            return 0;

        if (dp[row][col][direction])
            return dp[row][col][direction];

        dp[row][col][direction] = 1 + armLength(isMine, row + directions[direction], col + directions[direction+1], direction);
        return dp[row][col][direction];
    }*/
};

auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();

23348