<p>Given an <code>m x n</code> binary <code>matrix</code> filled with <code>0</code>&#39;s and <code>1</code>&#39;s, <em>find the largest square containing only</em> <code>1</code>&#39;s <em>and return its area</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg" style="width: 400px; height: 319px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/max2grid.jpg" style="width: 165px; height: 165px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 1
</pre>

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

<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;]]
<strong>Output:</strong> 0
</pre>

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

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>matrix[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        R,C = len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if (r,c) in dp:return dp[(r,c)]
            if r<0 or c<0 or r>=R or c>=C or matrix[r][c] == "0":
                return 0
            right = dfs(r+1,c)
            down = dfs(r,c+1)
            dia = dfs(r+1,c+1)
            res = 1 + min(right,dia,down)
            dp[(r,c)] = res
            return res
        
        res = 0
        for r in range(R):
            for c in range(C):
                if matrix[r][c] == "1":
                    res = max(res,dfs(r,c))
        return res**2






















        R,C = len(matrix),len(matrix[0])
        dp= {}
        def dfs(r,c):
            if (r,c) in dp:return dp[(r,c)]
            if r<0 or c<0 or r>=R or c>=C or matrix[r][c] == "0":return 0
            right = dfs(r,c+1)
            down = dfs(r+1,c)
            dia = dfs(r+1,c+1)
            res = 1 + min(right,down,dia)
            dp[(r,c)] = res
            return res
        res = 0
        for r in range(R):
            for c in range(C):
                if matrix[r][c] == "1":
                    res = max(res,dfs(r,c))
        return res**2














        R,C =len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if r<0 or c<0 or r>=R or c>=C or matrix[r][c]=="0":return 0
            if (r,c) in dp:return dp[(r,c)]
            right = dfs(r,c+1)
            down = dfs(r+1,c)
            dia = dfs(r+1,c+1)
            res = 1+min(right,down,dia)
            dp[(r,c)] = res
            return res
        res = 0
        for r in range(R):
            for c in range(C):
                if matrix[r][c]=="1":
                    res = max(res,dfs(r,c))
        return res**2


















        R,C =len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if r<0 or c<0 or r>=R or c>=C or matrix[r][c]=="0":return 0
            if (r,c) in dp:return dp[(r,c)]
            right = dfs(r,c+1)
            down = dfs(r+1,c)
            dia = dfs(r+1,c+1)
            res = 1+min(right,down,dia)
            dp[(r,c)] = res
            return res
        res = 0
        for r in range(R):
            for c in range(C):
                if matrix[r][c]=="1":
                    res = max(res,dfs(r,c))
        return res**2















        R,C= len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if (r,c) in dp:return dp[(r,c)]
            if r<0 or c<0 or r>=R or c>=C or matrix[r][c]=="0":return 0
            right = dfs(r+1,c)
            bot = dfs(r,c+1)
            dia = dfs(r+1,c+1)
            res = 1 + min(right,bot,dia)
            dp[(r,c)] = res
            return res 
        
        res = 0
        for r in range(R):
            for c in range(C):
                res = max(res,dfs(r,c))
        return res**2















        R,C = len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if (r,c) in dp:return dp[(r,c)]
            if r<0 or c<0 or r>=R or c>=C or matrix[r][c]!="1":return 0
            right = dfs(r,c+1)
            down = dfs(r+1,c)
            dia = dfs(r+1,c+1)
            res = 0
            if matrix[r][c]=="1":
                res = 1+min(right,down,dia)
            dp[(r,c)] = res
            return res
        res = 0
        for r in range(R):
            for c in range(C):
                res = max(res,dfs(r,c))
        return res**2

                























        R,C = len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if (r,c) in dp:return dp[(r,c)]
            if r<0 or c<0 or c>=C or r>=R or matrix[r][c]=="0":return 0
            down = dfs(r+1,c)
            right = dfs(r,c+1)
            dia = dfs(r+1,c+1)
            if matrix[r][c]=="1":
                res = 1+min(down,right,dia)
            dp[(r,c)] = res
            return res
        ans = 0
        for r in range(R):
            for c in range(C):
                ans = max(ans,dfs(r,c))
        return ans**2
            






















        R,C = len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if (r,c) in dp:return dp[(r,c)]
            if r<0 or c<0 or r>=R or c>=C:
                return 0
            right = dfs(r,c+1)
            bottom = dfs(r+1,c)
            dia = dfs(r+1,c+1)
            res = 0
            if matrix[r][c] == "1":
                res += 1 + min(right,bottom,dia)
            dp[(r,c)] = res
            return dp[(r,c)]
        res = 0
        for r in range(R):
            for c in range(C):
                if matrix[r][c] == "1":
                    res = max(res,dfs(r,c))
        return res**2



















        R,C = len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if (r,c) in dp:return dp[(r,c)]
            if r<0 or c<0 or r>=R or c>=C:return 0
            res = 0
            if matrix[r][c] == "1":
                res = 1 + min(dfs(r+1,c),dfs(r+1,c+1),dfs(r,c+1))
            dp[(r,c)] = res
            return dp[(r,c)]
        res=  0
        for r in range(R):
            for c in range(C):
                res = max(res,dfs(r,c))
        return res**2






















        R,C = len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if r<0 or c<0 or r>=R or c>=C:return 0
            if (r,c) in dp:return dp[(r,c)]
            right = dfs(r+1,c)
            bot = dfs(r,c+1)
            dia = dfs(r+1,c+1)
            res = 0
            if matrix[r][c] == "1":
                res = 1 + min(right,bot,dia)
            dp[(r,c)] = res
            return dp[(r,c)]





        res = 0
        for r in range(R):
            for c in range(C):
                res = max(res,dfs(r,c))
        return res**2






















        R,C = len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if r>=R or c>=C or c<0 or r<0:return 0
            if (r,c) in dp:return dp[(r,c)]
            right = dfs(r+1,c)
            dia = dfs(r+1,c+1)
            bot = dfs(r,c+1)
            res = 0
            if matrix[r][c] == '1':
                res+=1+min(right,bot,dia)
            dp[(r,c)] = res
            return dp[(r,c)]
        res = 0
        for r in range(R):
            for c in range(C):
                res = max(res,dfs(r,c))
        return res**2


























        R,C = len(matrix),len(matrix[0])
        dp = {}
        def dfs(r,c):
            if r<0 or c<0 or r>=R or c>=C:return 0
            if (r,c) in dp:return dp[(r,c)]
            right = dfs(r+1,c)
            down = dfs(r,c+1)
            dia = dfs(r+1,c+1)

            dp[(r,c)] = 0
            if matrix[r][c] == "1":
                dp[(r,c)] += 1 + min(right,down,dia)
            
            return dp[(r,c)]
        
        for r in range(R):
            for c in range(C):
                dfs(r,c)
        return max(dp.values())**2

































        R,C = len(matrix),len(matrix[0])
        memo = {}
        def dfs(r,c):
            if r<0 or c<0 or c>=C or r>=R :return 0
            if (r,c) in memo : return memo[(r,c)]
            right = dfs(r+1,c)
            down = dfs(r,c+1)
            dia = dfs(r+1,c+1)
            memo[(r,c)] = 0
            if matrix[r][c] == "1":
                memo[(r,c)] = 1+min(right,down,dia)
            return memo[(r,c)]
        for r in range(R):
            for c in range(C):
                dfs(r,c)
        return max(memo.values())**2




























        R,C = len(matrix),len(matrix[0])
        memo = {}
        def dfs(r,c):
            if r<0 or c<0 or r>=R or c>=C:
                return 0
            if (r,c) in memo:return memo[(r,c)]
            right = dfs(r+1,c)
            down = dfs(r,c+1)
            dia = dfs(r+1,c+1)
            memo[(r,c)] = 0
            if matrix[r][c] == "1":
                memo[(r,c)] = 1 + min(right,dia,down)
            return memo[(r,c)]
        for r in range(R):
            for c in range(C):
                dfs(r,c)
        return (max(memo.values()))**2

        







































































        row , col = len(matrix),len(matrix[0])
        cache = {}
        def dfs(r,c):
            if r>=len(matrix) or c>=len(matrix[0]):
                return 0
            if (r,c) in cache:
                return cache[(r,c)]
            down = dfs(r,c+1)
            right = dfs(r+1,c)
            dia = dfs(r+1,c+1)
            cache[(r,c)] = 0
            if matrix[r][c] == "1":
                cache[(r,c)] = 1 + min(down,right,dia)
            return cache[(r,c)]
        dfs(0,0)
        return max(cache.values())**2
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        row,col = len(matrix),len(matrix[0])
        cache = {}
        def dfs(r,c):
            if r>=row or c>=col:
                return 0
            if (r,c) not in cache:
                down = dfs(r+1,c)
                right = dfs(r,c+1)
                diag = dfs(r+1,c+1)
                
                cache[(r,c)] = 0
                if matrix[r][c] == "1":
                    cache[(r,c)] += 1 + min(down,right,diag)
            return cache[(r,c)]
        dfs(0,0)
        return max(cache.values())**2
        
        
56975