<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:
  int largest1BorderedSquare(vector<vector<int>>& grid) {
    int y = grid.size(), x = grid[0].size(), ans = 0;
    
    vector<vector<int>>l = grid, r = grid, u = grid, d = grid;
    
    for(int i = 0; i != y; i++){
      for(int j = 1; j != x; j++)
        if(r[i][j]) r[i][j] += r[i][j-1];
      for(int j = x-2; j >= 0; j--)
        if(l[i][j]) l[i][j] += l[i][j+1];
    }
    
    for(int j = 0; j != x; j++){
      for(int i = 1; i != y; i++)
        if(d[i][j]) d[i][j] += d[i-1][j];
      for(int i = y-2; i >= 0; i--)
        if(u[i][j]) u[i][j] += u[i+1][j];
    }
    
    for(int i = 0; i != y; i++)
      for(int j = 0; j != x; j++)
        if(l[i][j]){
          int sh = min(l[i][j],u[i][j]) - 1;
          
          for(;sh >= 0; sh--)
            if(r[i+sh][j+sh] > sh && d[i+sh][j+sh] > sh){
              ans = max(ans, (sh+1)*(sh+1));
              break;          
            }
        }
      
    return ans;
  }
};
15400