<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 {

    static inline uint32_t key(uint16_t i, uint16_t j) {
        return (i << 16 ) | j;
    }


    // counts number of increasing size plusses will fit at m,n
    // aka 1 means one k=2 sized plus
    // 2 means one k=2 and one k=3 sized plus. here is the dp relation
    
    std::unordered_map<uint32_t, bool> mines_; //quickah
    int n_;
    int max_arm_;
    // int solve(int i, int j) {


    //     // check center.
    //     if (mines_.find(key(i,j)) != mines_.end()) {
    //         //printf("mine at center %d %d\n", i, j);
    //         return 0;
    //     }
    //     //printf("Possible at %d %d\n", i, j);
    //     // solve smalles plus first then dp from there.
    //     for (int k=1;k<=max_arm_;k++) {

    //         // this can be brought out into max_arm;
    //         if ( i+k >= n_ || i - k < 0 || j + k >= n_ || j - k < 0 ) {
    //             //printf("bounds failed %d,%d %d\n", i ,j, k);
    //             return k;
    //         }

    //         bool mine_found = mines_.find(key(i,j-k)) != mines_.end() ||
    //             mines_.find(key(i,j+k)) != mines_.end() ||
    //             mines_.find(key(i-k,j)) != mines_.end() ||
    //             mines_.find(key(i+k,j)) != mines_.end();
    //         if (mine_found) {
    //             //printf("found a mine %d,%d %d\n", i ,j, k);
    //             return k;
    //         }

    //     }
    //     return 1;
    // }

    vector<vector<int>> horizontal_to_right;
    vector<vector<int>> horizontal_to_left;
    vector<vector<int>> vertical_down;
    vector<vector<int>> vertical_up;
    void print(const std::vector<std::vector<int>>&matrix) {
        for (int i=0;i<n_;i++) {
            const auto &row = matrix[i];            
            for (int j=0;j<n_;j++) {
                printf("%d ", row[j]);
            }
            printf("\n");
        }
    }

    void fillDP() {
        horizontal_to_right.resize(n_);
        vertical_down.resize(n_);
        for (int i=n_-1;i>=0;i--) {            
            vertical_down[i].resize(n_);
            auto &row = horizontal_to_right[i];
            row.resize(n_);
            for (int j=n_-1;j>=0;j--) {
                const auto k = key(i,j);
                // int add = mines_.find(k)==mines_.end() ? 1 : 0;                
                // row[j] = ((j < ( n_ -1 )) ? row[j+1] : 0 ) + add;                
                if (mines_.find(k)==mines_.end()) {
                    row[j] = ((j < ( n_ -1 )) ? row[j+1] : 0 ) + 1;
                } else {
                    row[j] = 0;
                }
            }
        }

        for (int i=n_-1;i>=0;i--) {                        
            for (int j=n_-1;j>=0;j--) {
                const auto k = key(i,j);
                // int add = mines_.find(k)==mines_.end() ? 1 : 0;                
                // vertical_down[i][j] = ((i < ( n_ -1 )) ? vertical_down[i+1][j] : 0 ) + add;                
                if (mines_.find(k)==mines_.end()) {
                    vertical_down[i][j] = ((i < ( n_ -1 )) ? vertical_down[i+1][j] : 0 ) + 1;                
                } else {
                    vertical_down[i][j] = 0;
                }
            }
        }  

        horizontal_to_left.resize(n_);
        vertical_up.resize(n_);
        for (int i=0;i<n_;i++) {            
            vertical_up[i].resize(n_);
            auto &row = horizontal_to_left[i];
            row.resize(n_);
            for (int j=0;j<n_;j++) {
                const auto k = key(i,j);
                if (mines_.find(k)==mines_.end()) {
                    row[j] = (( j > 0 ) ? row[j-1] : 0 ) + 1;
                } else {
                    row[j] = 0;
                }             
            }
        }

        for (int i=0;i<n_;i++) {                           
            for (int j=0;j<n_;j++) {
                const auto k = key(i,j);
                // int add = mines_.find(k)==mines_.end() ? 1 : 0;                
                // vertical_up[i][j] = ((i >0) ? vertical_up[i-1][j] : 0 ) + add;                
                if (mines_.find(k)==mines_.end()) {
                    vertical_up[i][j] = (( i > 0) ? vertical_up[i-1][j] : 0 ) + 1;                
                } else {
                    vertical_up[i][j] = 0;
                }                
            }
        }         
      
    }

    int solve() {
        int max_size = 0;
        for (int i=0;i<n_;i++) {                           
            for (int j=0;j<n_;j++) {
                const auto k = key(i,j);
                int add = mines_.find(k)==mines_.end() ? 1 : 0;                
                int v = std::min(std::min(std::min(vertical_down[i][j], vertical_up[i][j]), horizontal_to_right[i][j]), horizontal_to_left[i][j]);
                if ( v > max_size ) {
                    // printf("Found at %d %d val = %d\n", i, j, v);
                    max_size = v;
                }
            }
        }          
        return max_size;
    }

public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        if ( n < 1 ) {
            return 0;
        }
        
        n_ = n;
        max_arm_ = 1+ ((n_ ) >> 1) ; 
        // printf("Max K = %d\n", max_arm_);

        for (auto &v: mines) {
            const uint32_t k = key(v[0], v[1]);
            mines_[k] = 1;
        }

        // int max_size = 0;
        // for (int i=0;i<n;i++) {
        //     for (int j=0;j<n;j++) {
        //         const int v = solve(i,j);                
        //         max_size = std::max(v, max_size);                
        //     }
        // }
        fillDP();
        // printf("Horizontal right\n");
        // print(horizontal_to_right);
        // printf("Vertical down\n");
        // print(vertical_down);
        // printf("Horizontal left\n");
        // print(horizontal_to_left);
        // printf("Vertical up\n");
        // print(vertical_up);

        // for (int i=0;i<n;i++) {
        //     for (int j=0;j<n;j++) {
        //         const int v = solve(i,j);                
        //         max_size = std::max(v, max_size);                
        //     }
        // }
        return solve() ;
    }
};

73890