<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 {
    struct Lenghts {
        long up = -1;
        long down = -1;
        long left = -1;
        long right = -1;
    };

    enum Direction {
        Up,
        Down,
        Left,
        Right
    };


    void calcWithCenter(size_t i, size_t j, size_t n, Direction dir,
    std::vector<Lenghts> &preCalced, size_t &maxFound) {
        //std::cout << i << " " << j << std::endl;
        auto &cur = preCalced[i*n+j];

        if (dir == Left && cur.left == -1) {//not calced yet
            if ( i==0 ) {
                cur.left = 1;
            } else {
                calcWithCenter(i-1, j,  n, dir, preCalced, maxFound);
                cur.left = 1 + preCalced[(i-1)*n + j].left;
            }
        }
        if (dir == Up && cur.up == -1) {//not calced yet
            if ( j==0 ) {
                cur.up = 1;
            } else {
                calcWithCenter(i, j-1,  n, dir, preCalced, maxFound);
                cur.up = 1 + preCalced[i*n + j-1].up;
            }
        }
        if (dir == Right && cur.right == -1) {//not calced yet
            if ( i==n-1 ) {
                cur.right = 1;
            } else {
                calcWithCenter(i+1, j,  n, dir, preCalced, maxFound);
                cur.right = 1 + preCalced[(i+1)*n + j].right;
            }
        }                
        if (dir == Down && cur.down == -1) {//not calced yet
            if ( j==n-1 ) {
                cur.down = 1;
            } else {
                calcWithCenter(i, j+1,  n, dir, preCalced, maxFound);
                cur.down = 1 + preCalced[(i)*n + j+1].down;
            }
        }
    }

public:
    
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        std::vector<Lenghts> preCalced(n*n, Lenghts());

        for (const auto &mine : mines) {
            preCalced[mine[0]*n + mine[1]] = {0, 0, 0, 0};
        }
        size_t maxFound = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                auto &cur = preCalced[i*n+j];
                calcWithCenter(i, j, n, Left, preCalced, maxFound);
                calcWithCenter(i, j, n, Up, preCalced, maxFound);
                calcWithCenter(i, j, n, Right, preCalced, maxFound);
                calcWithCenter(i, j, n, Down, preCalced, maxFound);
                auto curArm = std::min(cur.left, std::min(cur.up, std::min(cur.right, cur.down)));
                if (curArm > maxFound) {
                     maxFound = curArm;
                }
            }
        }
        return maxFound;
        
    }
};
101359