<p>Given a 2D <code>grid</code> of <code>0</code>s and <code>1</code>s, return the number of elements in&nbsp;the largest <strong>square</strong>&nbsp;subgrid that has all <code>1</code>s on its <strong>border</strong>, or <code>0</code> if such a subgrid&nbsp;doesn&#39;t exist in the <code>grid</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1,1],[1,0,1],[1,1,1]]
<strong>Output:</strong> 9
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1,0,0]]
<strong>Output:</strong> 1
</pre>

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

<ul>
	<li><code>1 &lt;= grid.length &lt;= 100</code></li>
	<li><code>1 &lt;= grid[0].length &lt;= 100</code></li>
	<li><code>grid[i][j]</code> is <code>0</code> or <code>1</code></li>
</ul>
class Solution {
public:

    void fillrd(int r, int c, vector<vector<int>>&rd, int n, int m, vector<vector<int>>& grid){
        int rcnt = 0, ccnt = 0;
        for(int j=c; j<m; j++){
            if(grid[r][j] == 0) break;
            rcnt++;
        }
        for(int i=r; i<n; i++){
            if(grid[i][c] == 0) break;
            ccnt++;
        }
        rd[r][c] = min(rcnt,ccnt);
    }

    void filllu(int r, int c, vector<vector<int>>&lu, int n, int m, vector<vector<int>>& grid){
        int rcnt = 0, ccnt = 0;
        for(int j=c; j>=0; j--){
            if(grid[r][j] == 0) break;
            rcnt++;
        }
        for(int i=r; i>=0; i--){
            if(grid[i][c] == 0) break;
            ccnt++;
        }
        lu[r][c] = min(rcnt,ccnt);
    }

    int solve(int r, int c, vector<vector<int>>&rd,vector<vector<int>>&lu){
        for(int sz=rd[r][c]; sz>0; sz--){
            if(lu[r+sz-1][c+sz-1] >= sz) return sz;
        }
        return 1;
    }

    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>>rd(n,vector<int>(m));
        vector<vector<int>>lu(n,vector<int>(m));
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                fillrd(i,j,rd,n,m,grid);
                filllu(i,j,lu,n,m,grid);
            }
        }
        int ans = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(grid[i][j] == 1) ans = max(ans, solve(i,j,rd,lu));
            }
        }
        return ans*ans;
    }
};
14700