<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:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m,n=len(grid), len(grid[0])
        dpLeft = [[0] * n for _ in range(m)]
        dpRight = [[0] * n for _ in range(m)]
        dpUp = [[0] * n for _ in range(m)]
        dpDown = [[0] * n for _ in range(m)]

        for r in range(m):
            t = 0
            for c in range(n):
                dpLeft[r][c] = t
                if grid[r][c] == 1:
                    t+= 1
                else:
                    t = 0
        
        for r in range(m):
            t = 0
            for c in range(n-1, -1, -1):
                dpRight[r][c] = t
                if grid[r][c] == 1:
                    t+= 1
                else:
                    t = 0
        
        for c in range(n):
            t = 0 
            for r in range(m):
                dpUp[r][c] = t
                if grid[r][c] == 1:
                    t+= 1
                else:
                    t = 0
        
        for c in range(n):
            t = 0 
            for r in range(m-1, -1, -1):
                dpDown[r][c] = t
                if grid[r][c] == 1:
                    t+= 1
                else:
                    t = 0

        
        res = 0
        print(dpUp, dpDown)
        print(dpLeft, dpRight)
     
        for r in range(m):
            for c in range(n):
                print((r,c))
                if grid[r][c] != 1: continue
                right = dpRight[r][c]
                down = dpDown[r][c]
      
                res = max(res, 1)
                ma = min(right, down) + 1
                for k in range(1, ma):
                    if grid[r+k][c+k] != 1: continue
                    up = dpUp[r+k][c+k]
                    left = dpLeft[r+k][c+k]
                    if up >= k and left >= k:
                        res = max((k+1)**2, res)
                

             
     
        
        return res


  

17300