Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
 
Example 1:
Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:
Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

 
Constraints:

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

Difficulty: interview

Starter code:

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        
        for i in range(1, m):
            for j in range(1, n):
                if not matrix[i][j]:
                    continue
                if matrix[i][j-1] and matrix[i-1][j] and matrix[i-1][j-1]:
                    matrix[i][j] = min(matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1]) + 1
        
        total = 0
        for row in matrix:
            total += sum(row)
            
        return total
                


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp=matrix
        r = len(dp)
        c = len(dp[0])
        ans=0
        for i in range(1,r):
            for j in range(1,c):
                if(dp[i][j]==0):
                    continue
                if(dp[i-1][j]!=0 and dp[i-1][j-1]!=0 and dp[i][j-1]!=0):
                    dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
        for i in dp:
            ans+=sum(i)
        return ans

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        res=0
        dp=matrix
        r=len(dp)
        c=len(dp[0])
                  
        for i in range(1,r):
            for j in range(1,c):
                if dp[i][j]==0:
                    continue
                if dp[i-1][j]!=0 and dp[i-1][j-1]!=0 and dp[i][j-1]!=0:
                    dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1
        for i in dp:
            res+=sum(i)
        return res

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        count = 0
        size = 1
        maxSize = min(len(matrix), len(matrix[0]))
        prevInd = []
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 1:
                    count += 1
                    prevInd.append([i, j])
        while size <= maxSize and prevInd:
            newInd = []
            for ind in prevInd:
                row = ind[0]
                col = ind[1]
                add = True
                if row + size < len(matrix) and col + size < len(matrix[0]) :
                    for r in range(row, row + size + 1):
                        if not matrix[r][col + size]:
                            add = False
                            break
                    for c in range(col, col + size + 1):
                        if not matrix[row + size][c]:
                            add = False
                            break
                    if add:
                        count += 1
                        newInd.append([row, col])
            prevInd = newInd
            size += 1
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        res = 0
        n = len(matrix); m = len(matrix[0]) if matrix else 0
        for r in range(n):
            for c in range(m):
                if matrix[r][c] == 0: continue
                if r == 0 or c == 0: res += 1; continue
                matrix[r][c] = min(matrix[r-1][c-1], matrix[r][c-1], matrix[r-1][c]) + 1
                res += matrix[r][c]
        return res


class Solution:
    def validate_sub_matrix(self, matrix, rstart, cstart, size):
        for row in range(size + 1):
            for col in range(size + 1):
                if matrix[rstart + row][cstart + col] == 0:
                    return False
        return True
                
    def countSquares(self, matrix: List[List[int]]) -> int:
        count = 0
        num_rows = len(matrix)
        num_cols = len(matrix[0])
        for row in range(num_rows):
            for col in range(num_cols):
                if matrix[row][col] == 0:
                    continue
                    
                s_size = 0
                while row + s_size < num_rows and col + s_size < num_cols and self.validate_sub_matrix(matrix, row, col, s_size):
                    #print ((row, col, s_size))
                    count += 1
                    s_size += 1
        return count
                
                
                


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        M = len(matrix)
        N = len(matrix[0])
        
        ans = 0
        for i in range(M):
            for j in range(N):
                if matrix[i][j] == 1 and i>0 and j>0:
                    cand = min(matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1])
                    matrix[i][j] = (cand + 1)
                ans += matrix[i][j]
        return ans

class Solution:
    #iterate over every square and then fan out to n x n matrices and increment if all 1
    def countSquares(self, matrix: List[List[int]]) -> int:
        ret = 0
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if matrix[row][col] == 1:
                    sublen = 1
                    while row + sublen <= len(matrix) and col + sublen <= len(matrix[0]) and 0 not in [matrix[row+sublen-1][ncol] for ncol in range(col, col+sublen)] and 0 not in [matrix[nrow][col+sublen-1] for nrow in range(row, row+sublen)]:
                        ret += 1
                        sublen += 1
        return ret


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        res = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0: continue
                if i == 0 or j == 0:
                    res += matrix[i][j]
                else:
                    matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1])+1
                    res += matrix[i][j]
        return res
        
\"\"\"
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        res = 0
        for i in range(0,len(matrix)):
            for j in range(0,len(matrix[0])):
                if matrix[i][j] == 0: continue
                if i == 0 or j == 0:
                    res += matrix[i][j]
                    continue
                matrix[i][j] = min(matrix[i-1][j-1],matrix[i][j-1],matrix[i-1][j]) + 1
                #maxS = max(maxS, matrix[i][j])
                res += matrix[i][j]
                #print('res:',res)
        '''
        res = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                for z in range(maxS):
                    if matrix[i][j] > z: res += 1
        '''
        print(matrix)
        return res
\"\"\"
                
        

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        res = 0
        n, m = len(matrix), len(matrix[0])
        for r in range(n):
            for c in range(m):
                if matrix[r][c] == 0: continue
                if r == 0 or c == 0: res += 1; continue
                matrix[r][c] = min(matrix[r-1][c-1], matrix[r][c-1], matrix[r-1][c]) + 1
                res += matrix[r][c]
        return res


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        # for each item we count how many squares there are such that this item is
        # the bottom right point in the square.
        # this is equivalent to \"what is the largest square containing this item as
        # its bottom right point\"
        # so we calculate for each item what is the largest square that contains him as the bottom right
        # point, and then sum the results

        # we calculate this using dynamic programming
        # for the first row and column, the answer is already there
        total = sum(matrix[0])

        for i in range(1, len(matrix)):
            total += matrix[i][0]
            for j in range(1, len(matrix[i])):
                if matrix[i][j] == 0:
                    continue
                matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1
                total += matrix[i][j]

        return total

class Solution:
    def countSquares(self, a: List[List[int]]) -> int:
        d=[]
        r=len(a)+1
        c=len(a[0])+1
        d=[[0 for j in range(c)] for i in range(r)]
        for i in range(1,r):
            for j in range(1,c):
                if(a[i-1][j-1]==1):
                    d[i][j]=1+min(d[i-1][j],d[i][j-1],d[i-1][j-1])
        print(d)
        return sum(map(sum,d))


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m,n=len(matrix),len(matrix[0])
        res=0
       
        for r in range(m):
            for c in range(n):
                if matrix[r][c]==0:
                    continue
                if r==0 or c==0:
                    res+=1
                else:                
                    cell_val = min(matrix[r-1][c-1], matrix[r][c-1], matrix[r-1][c]) + matrix[r][c]
                    res += cell_val
                    matrix[r][c] = cell_val 
              
        return res

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                if matrix[i][j]==1:
                    matrix[i][j] = min(matrix[i-1][j],matrix[i][j-1],matrix[i-1][j-1])+1
        return sum(sum(i) for i in matrix)

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        ans = 0
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                temp = matrix[row][col]
                ans += matrix[row][col]
                if(row > 0):
                    matrix[row][col] += matrix[row-1][col]
                if(col > 0):
                    matrix[row][col] += matrix[row][col-1]
                if(row > 0 and col > 0):
                    matrix[row][col] -= matrix[row-1][col-1]
                if not temp: continue
                side = 1
                while(row-side >= 0 and col-side >= 0):
                    s = matrix[row][col]
                    if(col-side > 0):
                        s -= matrix[row][col-side-1]
                    if(row-side > 0):
                        s -= matrix[row-side-1][col]
                    if(col-side > 0 and row-side > 0):
                        s += matrix[row-side-1][col-side-1]
                    if(s == (side+1)*(side+1)):
                        ans += 1
                    else:
                        break
                    side += 1
        return ans

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m,n = len(matrix), len(matrix[0])
        dp = [[0] * (n+1) for _ in range(m+1)]
        result = 0
        
        for i in range(m):
            for j in range(n):
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j] + matrix[i][j]
        
        for i in range(m):
            for j in range(n):
                for l in range(1,min(m-i,n-j)+1):
                    expected_sum = l**2
                    x,y = i+l, j+l
                    range_sum = dp[x][y] - dp[x][j] - dp[i][y] + dp[i][j]
                    # print(i,j,l,x,y)
                    # print(expected_sum, range_sum)
                    if expected_sum != range_sum:
                        break
                    result += 1
                        
        return result

class Solution:
    def memoization(self, grid, i, j, memo):
        if i == len(grid)-1 or j == len(grid[0])-1:
            return int(grid[i][j] == 1)
        if memo[i][j] is None:
            if grid[i][j] == 0:
                memo[i][j] = 0
            else:
                col = self.memoization(grid, i, j+1, memo)
                row = self.memoization(grid, i+1, j, memo)
                diag = self.memoization(grid, i+1, j+1, memo)
                memo[i][j] = min(min(col, row), diag) + 1
        return memo[i][j]
                
    def countSquares(self, matrix: List[List[int]]) -> int:
        memo = [[None for j in range(len(matrix[0]))] for i in range(len(matrix))]
        out = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                out += self.memoization(matrix, i, j, memo)
        return out

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        
        matrix_sum = [ [0]*(n+1) for _ in range(m+1) ]
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                matrix_sum[i][j] = matrix_sum[i][j-1] + matrix[i-1][j-1]
        
        for j in range(1, n+1):
            for i in range(1, m+1):
                matrix_sum[i][j] = matrix_sum[i][j] + matrix_sum[i-1][j]
        
        cnt = 0
        
        for i in range(1, m+1):
            for j in range(1, n+1):
                size = 1
                while size <= min(i,j):
                    total = matrix_sum[i][j] + matrix_sum[i-size][j-size] - matrix_sum[i-size][j]\\
                    - matrix_sum[i][j-size]
                    if total == size*size:
                        cnt += 1
                    else:
                        break
                    size += 1
        
        return cnt
        
        

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        ans = 0
        topleft = [0 for i in matrix[0]]
        totop = [0 for i in matrix[0]]
        for i in range(len(matrix)):
            toleft, nextarea = 0, [0 for i in range(len(matrix[0])+1)]
            for j in range(len(matrix[0])):
                if matrix[i][j] == 1:
                    totop[j] += 1
                    toleft += 1
                    maxr = min(totop[j], toleft, topleft[j] + 1)
                    nextarea[j + 1] = maxr
                    ans += maxr
                else:
                    totop[j] = 0
                    toleft = 0
                    nextarea[j + 1] = 0
            topleft = nextarea
        return ans

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    dp[i+1][j+1] = min(dp[i][j+1], min(dp[i+1][j], dp[i][j])) + 1
        
        cnts = [0 for _ in range(min(m, n) + 1)]
        for i in range(1, min(m, n) + 1):
            cnts[i] = i ** 2 + cnts[i-1]
        
        res = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                res += dp[i][j]
        return res

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        totalRows = len(matrix)
        totalColumns = len(matrix[0])
        longestStreak = [[(0,0,0) for i in range(totalColumns)] for j in range(totalRows)]
        total = 0
        for i in range(totalRows):
            for j in range(totalColumns):
                if(i == 0 and j == 0):
                    longestStreak[i][j] = (matrix[i][j],matrix[i][j],matrix[i][j])
                    total += matrix[i][j]
                else:
                    if(i == 0):
                        longestStreak[i][j] = (matrix[i][j]*(longestStreak[i][j-1][0]+1),matrix[i][j],matrix[i][j])
                        total += matrix[i][j]
                    elif(j == 0):
                        longestStreak[i][j] = (matrix[i][j],matrix[i][j]*(longestStreak[i-1][j][1]+1),matrix[i][j])
                        total += matrix[i][j]
                    else:
                        a = matrix[i][j]*(longestStreak[i][j-1][0]+1)
                        b = matrix[i][j]*(longestStreak[i-1][j][1]+1)
                        c = matrix[i][j]*(longestStreak[i-1][j-1][2]+1)
                        longestStreak[i][j] = (a,b,min([a,b,c]))
                        total += min([a,b,c])
        return total

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        def is_ones(lst, n, i, j):
            ones = 0
            for ix in range(i, i + n):
                for jy in range(j, j + n):
                    if lst[ix][jy] == 1:
                        ones += 1
            return ones == n*n
        
        n = len(matrix)
        m = len(matrix[0])
        ans = 0
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 1:
                    tmp = 1
                    while (i + tmp <= n) and (j + tmp <= m):
                        if is_ones(matrix, tmp, i, j):
                            ans += 1
                            tmp += 1
                        else:
                            break
        return ans

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        ans=0
        n=len(matrix)
        m=len(matrix[0])
        pre=[[0 for i in range(m+1)] for j in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                if matrix[i-1][j-1]==1:
                    ans+=1
                pre[i][j]=matrix[i-1][j-1]
                if i-1>=0:
                    pre[i][j]+=pre[i-1][j]
                if j-1>=0:
                    pre[i][j]+=pre[i][j-1]
                if i-1>=0 and j-1>=0:
                    pre[i][j]-=pre[i-1][j-1]
                c=2
                while i-c>=0 and j-c>=0:
                    if pre[i][j]-pre[i][j-c]-pre[i-c][j]+pre[i-c][j-c]==c**2:
                        ans+=1
                    else:
                        break
                    c+=1
        return ans


from itertools import accumulate
from typing import List

def transpose(m):
    return list(map(list, zip(*m)))

def prefix_sums(m):
    return [list(accumulate(r)) for r in m]


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0

        bsums = transpose(prefix_sums(transpose(prefix_sums(matrix))))
        squares = 0
        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            for j in range(n):
                k = 0
                while i + k < m and j + k < n:
                    s = bsums[i+k][j+k]
                    if i > 0: s -= bsums[i -1][j + k]
                    if j > 0: s -= bsums[i + k][j - 1]
                    if i > 0 and j > 0: s += bsums[i - 1][j - 1]
                    if s == (k + 1) ** 2:
                        squares += 1
                    else:
                        break
                    k += 1
        return squares

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        row, col = len(matrix), len(matrix[0])
        res = 0
        #if 
        
        for r in range(row):
            for c in range(col):
                if matrix[r][c] == 1:
                    if r==0 or c==0:
                        res+=1
                    else:
                        val= min(matrix[r-1][c],matrix[r][c-1],matrix[r-1][c-1])+matrix[r][c]
                        res+=val
                        matrix[r][c]=val
        return res

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        def countHelper(r: int, c: int, size: int = 0) -> int:
            if r + size >= rMax or c + size >= cMax:
                return 0
            
            rowOnes = rSums[r + size][c + size]
            if c > 0:
                rowOnes -= rSums[r + size][c - 1]
            colOnes = cSums[c + size][r + size]
            if r > 0:
                colOnes -= cSums[c + size][r - 1]

            return 1 + countHelper(r, c, size + 1) if rowOnes == colOnes == size + 1 else 0
            
        rMax = len(matrix)
        cMax = len(matrix[0])
        
        rSums = [[0] * cMax for _ in range(rMax)]
        cSums = [[0] * rMax for _ in range(cMax)]
        for r, row in enumerate(matrix):
            for c, sq in enumerate(row):
                rSums[r][c] = cSums[c][r] = matrix[r][c]
                if c > 0:
                    rSums[r][c] += rSums[r][c - 1]
                if r > 0:
                    cSums[c][r] += cSums[c][r - 1]
                    
        totalSquares = 0
            
        for r, row in enumerate(matrix):
            for c, sq in enumerate(row):
                if sq == 1:
                    totalSquares += countHelper(r, c)
                    
        return totalSquares


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        m = len(matrix)
        n = len(matrix[0])
        res = 0
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    dp[i+1][j+1] = min(dp[i+1][j],dp[i][j+1],dp[i][j]) + 1
                    res += dp[i+1][j+1]
        return res
        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        memo = {}
        def recursive(row, col):
            if 0 <= row < len(matrix) and 0<= col < len(matrix[0]) and matrix[row][col] == 1:
                nextRow = recursive(row+1, col)
                nextCol = recursive(row, col+1)
                nextDiag = recursive(row+1, col+1)
                return min(nextRow, nextCol, nextDiag) + 1
            return 0
        
        def cached(row, col):
            pair = (row, col)
            if pair in memo: return memo[pair]
            if 0 <= row < len(matrix) and 0 <= col < len(matrix[0]) and matrix[row][col] == 1:
                nextRow = cached(row+1, col)
                nextCol = cached(row, col+1)
                nextDiag = cached(row+1, col+1)
                memo[pair] = min(nextRow, nextCol, nextDiag)+1
                return memo[pair]
            return 0
            
        count = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                count += cached(i, j)
        return count


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        sq = 0
        m_row = range(len(matrix))
        m_col = range(len(matrix[0])) 
        
        def expand_square(row, n, m, p, square=0, count=1):
            while count > -1:
                print(count, square)
                for i in range(count):
                    if row + i == m:
                        return square
                    for j in range(count):
                        if n + j == p:
                            return square
                        elif matrix[row + i][n + j] != 1:
                            return square                
                square += 1
                count += 1
        
        for row in m_row:
            for n in m_col:
                if matrix[row][n] == 1:
                    sq += expand_square(row, n, len(matrix), len(matrix[0]))

                                    
        return sq

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:

        rownum = len(matrix)
        if rownum < 1 : return 0
        colnum = len(matrix[0])
        if colnum < 1: return 0

        aux3 = defaultdict(lambda : -1)
        def check(r, c): # (r, c) 를 기준으로 할 때 가장 긴 길이를 반환 
            if r < 0 or r >= rownum or c < 0 or c >= colnum:
                return 0
            elif matrix[r][c] == 0:
                return 0
            else:
                if aux3[(r, c)] != -1:
                    return aux3[(r, c)]
                else:
                    c1 = check(r+1, c)                
                    c2 = check(r, c+1)
                    c3 = check(r+1, c+1)
                    aux3[(r, c)] =  min(c1, c2, c3) + 1
                    return aux3[(r, c)]
        ret = 0
        # aux4 =[]
        for r in range(0, rownum):
            for c in range(0, colnum):
                if matrix[r][c] == 1:
                    max_len = check(r, c)
                    ret += max_len
        return ret        

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n, m = len(matrix), len(matrix[0])
        
        dp = [matrix[0][j] for j in range(m)]
        count = sum(dp)
        
        for i in range(1, n):
            new_dp = [matrix[i][j] for j in range(m)]
            
            for j in range(1, m):
                if matrix[i][j] == 1:
                    new_dp[j] = min(dp[j], new_dp[j-1], dp[j-1]) + 1
            
            dp = new_dp
            count += sum(dp)
        
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        dp = [0 for i in range(cols + 1)]
        tot = 0
        for i in range(rows):
            for j in range(cols):
                if not matrix[i][j]:
                    dp[j + 1] = 0
                    continue
                if dp[j + 1] == dp[j]:
                    dp[j + 1] += 1 if matrix[i - dp[j]][j - dp[j]] else 0 
                else:    
                    dp[j + 1] = min(dp[j + 1], dp[j]) + 1
                tot += dp[j + 1]
        return tot 

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
#         def is_valid_square(start_row, end_row, start_col, end_col, matrix):
#             for row in range(start_row, end_row + 1):
#                 for col in range(start_col, end_col + 1):
#                     if matrix[row][col] != 1:
#                         return False
            
#             return True  
        
        result = 0
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                search_space_increase = 0
                while row + search_space_increase < len(matrix) and col + search_space_increase < len(matrix[0]):
                    end_row = row + search_space_increase 
                    end_col = col + search_space_increase
                    
                    is_valid = True
                    for start_row in range(row, end_row + 1):
                        for start_col in range(col, end_col + 1):
                            if matrix[start_row][start_col] != 1:
                                is_valid = False
                                break
                        if not is_valid:
                            break
                    
                    if not is_valid:
                        break
                        
                    result += 1
                    search_space_increase += 1
                        
        
        return result

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
            # If matrix is empty: return 0
        if not matrix:
            return 0

        # For every '1' encountered, increment count by 1

        # Count the number of '1s' for each row
        #    Unsure yet: record start, and stop index
        
        count = 0
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if matrix[row][col] == 1:
                    if row == 0 or col == 0:
                        count += 1
                    else:
                        cell = min(matrix[row-1][col], matrix[row-1][col-1], matrix[row][col-1]) + matrix[row][col]
                        count += cell
                        matrix[row][col] = cell
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        res = 0 
        for i in range(n):
            for j in range(m):
                # count the number of square with left-top corner be res[i][j]
                done = False
                new_i = i
                new_j = j
                
                while 0 <= new_i < n and 0 <= new_j < m and not done:
                    area = 0 
                    for k in range(i,new_i + 1):
                        area += matrix[k][new_j]
                    for k in range(j, new_j + 1):
                        area += matrix[new_i][k]
                    area -= matrix[new_i][new_j]
                        
                    if area == new_j - j + new_i- i + 1:
                        res += 1
                        new_i = new_i + 1
                        new_j = new_j + 1
                    else:
                        done = True
        return res
        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        \"\"\"
        Brute force, for each position (i,j) calculate the
        number of square matrices ending at (i,j) and 
        return the total sum of all numbers for all (i,j).
        
        This would cost O(m*n*m*n) time complexity. We can speed
        this up by taking advantage of the fact that such square
        submatrices ending at (i,j) must build off of previous
        submatrices. That is if we know the number of square
        submatrices of ones at (i-1,j-1), (i,j-1) and (i-1,j)
        then we can compute the number for (i,j).
        
        Concretely, the square[i][j] must equal 
            min(
                square[i-1][j-1],
                square[i-1][j],
                square[i][j-1]
            ) + 1
        
        \"\"\"
        ans = 0
        
        m = len(matrix)
        n = len(matrix[0])
        # Cache the number of square submatrices ending at current coordinate
        dp = [0] * n
        for i in range(m):
            squares_at_ij = 0
            new_dp = [0] * n
            for j in range(n):
                if matrix[i][j] == 1:
                    squares_at_ij = min(
                        dp[j], dp[j-1] if j > 0 else 0, squares_at_ij
                    ) + 1
                else: 
                    squares_at_ij = 0
                ans += squares_at_ij
                new_dp[j] = squares_at_ij
            dp = new_dp
        return ans

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        res = 0 
        for i in range(n):
            for j in range(m):
                
                done = False
                end_i = i
                end_j = j
                
                while 0 <= end_i < n and 0 <= end_j < m and not done:
                    #  check the squre of [i, new_i] * [j, new_j]
                    area = 0 
                    for k in range(i,end_i + 1):
                        area += matrix[k][end_j]
                    for k in range(j, end_j + 1):
                        area += matrix[end_i][k]
                    area -= matrix[end_i][end_j]
                        
                    if area == end_j - j + end_i- i + 1:
                        res += 1
                        end_i += 1
                        end_j += 1
                    else:
                        done = True
        return res
        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix: return 0
        m, n = len(matrix), len(matrix[0])

        diag = 0
        mem = [0 for _ in range(n)]

        res = 0
        for i in range(n):
            mem[i] = matrix[0][i]
            res += mem[i]

        for i in range(1,m):
            for j in range(n):
                tmp = mem[j]
                if matrix[i][j] == 0: mem[j] = 0
                elif j == 0:
                    mem[j] = matrix[i][j]
                    res += mem[j]
                else:
                    mem[j] = min(diag, mem[j-1], mem[j])+1
                    res += mem[j]
                diag = tmp
        return res


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        rows = len(matrix)
        if (rows == 0):
            return 0
        
        cols = len(matrix[0])
        if (cols == 0):
            return 0
        
        self.res = 0
        
        for r in range(rows):
            for c in range(cols):
                if (matrix[r][c] == 1):
                    if (r == 0 or c == 0):
                        self.res += 1
                    else:
                        cell_val = min(matrix[r-1][c-1], matrix[r-1][c], matrix[r][c-1]) + 1
                        self.res += cell_val
                        matrix[r][c] = cell_val
                        
        return self.res

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        res = 0 
        for i in range(n):
            for j in range(m):
                
                done = False
                new_i = i
                new_j = j
                
                while 0 <= new_i < n and 0 <= new_j < m and not done:
                    #  check the squre of [i, new_i] * [j, new_j]
                    area = 0 
                    for k in range(i,new_i + 1):
                        area += matrix[k][new_j]
                    for k in range(j, new_j + 1):
                        area += matrix[new_i][k]
                    area -= matrix[new_i][new_j]
                        
                    if area == new_j - j + new_i- i + 1:
                        res += 1
                        new_i = new_i + 1
                        new_j = new_j + 1
                    else:
                        done = True
        return res
        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if matrix is None or len(matrix)==0:
            return 0
        r=len(matrix)
        c=len(matrix[0])
        res=0
        for i in range(r):
            for j in range(c):
                if(matrix[i][j]==1):
                    if(i==0 or j==0):
                        res+=1
                    else:
                        k=min(matrix[i-1][j-1],matrix[i-1][j],matrix[i][j-1])+matrix[i][j]
                        res+=k
                        matrix[i][j]=k
        return res


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        dp = [0 for i in range(cols + 1)]
        tot = 0
        for i in range(rows):
            for j in range(cols):
                if not matrix[i][j]:
                    dp[j + 1] = 0
                    continue
                length = min(dp[j + 1], dp[j]) 
                dp[j + 1] = length + matrix[i - length][j - length]
                tot += dp[j + 1]
        return tot 

class Solution:
    def countSquares(self, A: List[List[int]]) -> int:
            
        for i in range(1, len(A)):
            for j in range(1, len(A[0])):
                A[i][j] *= min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1]) + 1
        return sum(map(sum, A))

class Solution:
    class Graph:
        def __init__(self, g):
            self.r = len(g)
            self.c = len(g[0])
            self.graph = g
        def isSafe(self, r, c, notvisited):
            return r >=0 and r<self.r and c>=0, c<self.c and notvisited[r][c] and self.graph[r][c] == 1

    def countSquares(self, matrix: List[List[int]]) -> int:
        r, c = len(matrix), len(matrix[0])
        dp = [[0]*(c+1) for _ in range(r+1)]
        cnt = 0
        for i in range(r):
            for j in range(c):
                if matrix[i][j] == 1:
                    dp[i+1][j+1] = min(dp[i+1][j], dp[i][j], dp[i][j+1]) + 1
                    cnt +=dp[i+1][j+1]
        return cnt
                


class Solution:
    def countSquares(self, A):
        for i in range(1, len(A)):
            for j in range(1, len(A[0])):
                A[i][j] *= min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1]) + 1
        return sum(map(sum, A))


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n+1) for _ in range(m+1)] # new int[m+1][n+1];
        ans = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j]:
                    dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1
                    ans += dp[i+1][j+1]
        return ans
        
        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])
        
        count = 0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 1:
                    print((r,c))
                    size =  0
                    notOne = False
                    while not notOne and r+size <= rows-1 and c+size <= cols-1:
                        for p in range(size+1):
                            if matrix[r+p][c+size] != 1 or matrix[r+size][c+p] != 1:
                                notOne = True
                                break
                        if matrix[r+size][c+size] != 1: notOne = True        
                        if not notOne: count += 1 
                        size += 1
                        print (size)
                        print(count)
                    
        return count
    



class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        def get(i, j):
            if i < 0 or j < 0:
                return 0
            elif i > len(matrix) or j > len(matrix[0]):
                return 0
            
            return matrix[i][j]
        
        m = len(matrix)
        n = len(matrix[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] != 1:
                    continue
                squares = min(get(i-1, j-1), get(i-1, j), get(i, j-1)) + 1
                matrix[i][j] = squares
                count += squares
                
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        row, col = len(matrix), len(matrix[0])
        
        count = 0
        for i in range(row):
            for j in range(col):
                if(matrix[i][j]):
                    if(i == 0 or j == 0):
                        count += 1
                    else:
                        check_val = min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1])
                        count += check_val+1
                        matrix[i][j] = check_val+1
        
        return count

class Solution:
    def countSquares(self, dp):
        if len(dp)==0 or len(dp[0])==0:
            return 0
        for i,row in enumerate(dp):
            for j,val in enumerate(row):
                if val==1:
                    left=dp[i][j-1] if j>0 else 0
                    up=dp[i-1][j] if i>0 else 0
                    diag=dp[i-1][j-1] if i>0 and j>0 else 0
                    dp[i][j]=min((left,up,diag))+1
                else:
                    dp[i][j]=0
        return sum(map(sum,dp))


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        height, width= len(matrix), len(matrix[0])
        n = 0
        
        def n_squares(x, y):
            
            length = 0
            
            if not matrix[y][x]:
                return 0
            
            while x + length + 1 <= width  and y + length + 1 <= height:
                
                content = [row[x: x + length + 1] for row in matrix[y: y + length + 1]]
                if not all(i for j in content for i in j):
                    break
                    
                length += 1
                
            return length
        
        for x in range(width):
            for y in range(height):
                n += n_squares(x, y)
        
        return n

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def do_dfs(r,c):
            \"\"\"Recursive DFS\"\"\"
            res = float('inf')

            for move in moves:
                cand_row = r + move[0]
                cand_col = c + move[1]

                if check_validity(cand_row, cand_col):
                    res = min(res, do_dfs(cand_row, cand_col))
                else:
                    res = 0
            res += 1 #The square itself is a one-sided sq because it is 1
            total_squares[0] += res
            print (r,c, res)
            return res
        
        def check_validity(r,c):
            \"\"\"Check if r,c is in-bounds and equal to 1 \"\"\"

            if 0<=r<R and 0<=c<C and matrix[r][c]==1 :
                return True

            return False

        total_squares = [0]

        if not matrix:
            return total_squares[0]

        moves = ((0,1),(1,1),(1,0))

        R,C = len(matrix), len(matrix[0])

        for r in range(R):
            for c in range(C):
                if check_validity(r,c):
                    do_dfs(r,c)

        return total_squares[0]


class Solution:
    def countSquares(self, M: List[List[int]]) -> int:
        if not M:
            return 0
        m,n = len(M), len(M[0])
        
        rowCounts = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if M[i][j]:
                    rowCounts[i][j] = 1+rowCounts[i][j-1] if j>0 else 1
        
        colCounts = [[0]*n for _ in range(m)]
        for j in range(n):
            for i in range(m):
                if M[i][j]:
                    colCounts[i][j]=1+colCounts[i-1][j] if i>0 else 1
               
        dp = [[0]*n for _ in range(m)]
        out=0
        for i in range(m):
            for j in range(n):
                if M[i][j]:
                    if i==0 or j ==0:
                        dp[i][j] = min(rowCounts[i][j],colCounts[i][j])
                    else:
                        dp[i][j] = min(rowCounts[i][j],colCounts[i][j],1+dp[i-1][j-1])
                    out+=dp[i][j]
        return out


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        N = len(matrix)
        M = len(matrix[0])
        result = [[0 for j in range(M)] for i in range(N)]
        ss = 0
        for i in range(N):
            for j in range(M):
                if i == 0 or j == 0:
                    result[i][j] = matrix[i][j]
                else:
                    result[i][j] = matrix[i][j] * (1 + min(
                            min(result[i-1][j],
                                result[i][j-1]
                            ),
                            result[i-1][j-1],
                    ))
                ss += result[i][j]
        return ss

class Solution:
    #iterate over every square and then fan out to n x n matrices and increment if all 1
    def countSquares(self, matrix: List[List[int]]) -> int:
        ret = 0
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if matrix[row][col] == 1:
                    sublen = 1
                    check = 1
                    while check == 1 and row + sublen <= len(matrix) and col + sublen <= len(matrix[0]):
                        for ncol in range(col, col+sublen):
                            if matrix[row+sublen-1][ncol] == 0:
                                check = 0
                                break
                        for nrow in range(row, row+sublen):
                            if matrix[nrow][col+sublen-1] == 0:
                                check = 0
                                break
                        sublen += 1
                        ret += check
        return ret


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]

        squares = 0
        for i in range(m):
            for j in range(n):
                if not matrix[i][j]:
                    continue

                dp[i][j] = 1
                if i > 0 and j > 0:
                    dp[i][j] += min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
                squares += dp[i][j]

        return squares

from itertools import chain as chain

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                if matrix[i][j] == 1:
                    matrix[i][j] = 1+min(matrix[i-1][j],matrix[i][j-1],matrix[i-1][j-1])
                else:
                    matrix[i][j] = 0
                    
        return sum(chain(*matrix))

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp=[[0 for _ in range(len(matrix[0]))]for _ in range(len(matrix))]
        summ=0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i==0 or j==0:
                    dp[i][j]=matrix[i][j]
                else:
                    if matrix[i][j]==0:
                        dp[i][j]=0
                    else:
                        dp[i][j]=1+min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])
                summ+=dp[i][j]
        return summ


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n=len(matrix)
        m=len(matrix[0])
        a=0
        for i in range(n):
            for j in range(m):
                if matrix[i][j]==1:
                    if i==0 or j==0:
                        a+=1
                    else:
                        t=min(matrix[i-1][j-1],matrix[i-1][j],matrix[i][j-1])+matrix[i][j]
                        a+=t
                        matrix[i][j]=t
        return a
                        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n,m = len(matrix), len(matrix[0])
        for i in range(1,n):
            for j in range(1,m):
                if matrix[i][j]:
                    matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1
        return sum(sum(x) for x in matrix)

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        # we count for each item, how many squares there are such that this item is 
        # the bottom right point in the square
        # this is equivalent to what is the largest square containing this item as 
        # its bottom right point
        # so we calculate for each item what is the largest square that contains him as the bottom right
        # point, and then sum all the results
        
        # we calculate this using dynamic programming
        # for the first row and column, the answer is already there
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[i])):
                if matrix[i][j] == 0:
                    continue
                matrix[i][j] = min(matrix[i - 1][j], matrix[i][j- 1], matrix[i - 1][j- 1]) + 1
        
        total = 0
        for i in range(0, len(matrix)):
            for j in range(0, len(matrix[i])):
                total+= matrix[i][j]
                
        return total


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        sqrsCnt = 0
        for y, row in enumerate(matrix):
            for x, val in enumerate(row):
                i, j = x, y
                while True:
                    if i < 0 or j < 0: break
                    if any(matrix[j][a] != 1 for a in range(i,x+1)): break
                    if any(matrix[b][i] != 1 for b in range(j,y+1)): break
                    if matrix[j][i] != 1: break
                    sqrsCnt += 1
                    i, j = i-1, j-1
        return sqrsCnt

from collections import defaultdict
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        num_right = defaultdict(lambda: 0)
        num_below = defaultdict(lambda: 0)
        m = len(matrix)
        n = len(matrix[0])
        
        for i in reversed(range(m)):
            for j in reversed(range(n)):
                if j+1 < n:
                    num_right[(i,j)] = num_right[(i, j+1)] + 1 if matrix[i][j+1] == 1 else num_right[(i, j+1)]
                else:
                    num_right[(i,j)] = 0
                if i+1 < m:
                    num_below[(i,j)] = num_below[(i+1, j)] + 1 if matrix[i+1][j] == 1 else num_below[(i+1, j)]
                else:
                    num_below[(i,j)] = 0
                
        count = 0
        partial = defaultdict(lambda: 0)
        for i in reversed(range(m)):
            for j in reversed(range(n)):
                if matrix[i][j] == 0:
                    continue
                r = num_right[(i,j)]
                d = num_below[(i,j)]
                # print('******************')
                # print('Index', i,j)
                # print('Counts', r,d)
                # print(count)
                # print(partial)
                if matrix[i][j] == 1:
                    partial[(i,j,1)] = 1
                    count += 1
                diff = min(r,d)
                flag = True
                for k in range(2, diff+2):
                    #print('Checking k=', k)
                    if partial[(i, j+1, k-1)] == 1 and partial[(i+1, j+1, k-1)] == 1 and partial[(i+1, j, k-1)] == 1:
                        partial[(i,j,k)] = 1
                        count += 1
                    else:
                        flag = False
                    if not flag:
                        break
                    
        #print(count)
        return count       

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        import copy
        def grow_sqaure(x, y):
            oriX = copy.copy(x)
            oriY = copy.copy(y)
            still_square = False
            count = 0
            if matrix[x][y] == 1:
                still_square = True
            while x < len(matrix) and y < len(matrix[0]) and still_square:
                for i in range(oriX, x+1):
                    if matrix[i][y] != 1:
                        return count

                for i in range(oriY, y+1):
                    if matrix[x][i] != 1:
                        return count
                count += 1
                x += 1
                y += 1
            return count

        count = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):

                count += grow_sqaure(i, j)
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        row = len( matrix)
        col = len(matrix[0])
        ret =0
        
        for r in range(row):
            for c in range(col):
                if matrix[r][c] == 1:
                    if r == 0 or c == 0: ret += 1
                    else:
                        matrix[r][c]= min(matrix[r-1][c-1],matrix[r-1][c],matrix[r][c-1]) + 1
                        ret += matrix[r][c]
        return ret

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        import copy
        def grow_sqaure(x, y):
            oriX = copy.copy(x)
            oriY = copy.copy(y)
            
            count = 0
            if matrix[x][y] == 1:
                still_square = True
            while x < len(matrix) and y < len(matrix[0]):
                for i in range(oriX, x+1):
                    if matrix[i][y] != 1:
                        return count

                for i in range(oriY, y+1):
                    if matrix[x][i] != 1:
                        return count
                count += 1
                x += 1
                y += 1
            return count

        count = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):

                count += grow_sqaure(i, j)
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp = [[matrix[i][j] for j in range(len(matrix[0]))] for i in range(len(matrix))]
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if matrix[i][j] == 0:
                    continue
                if dp[i-1][j] != 0 and dp[i][j-1] != 0 and dp[i-1][j-1] != 0:
                    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
        count = 0
        for row in dp:
            count += sum(row)
        return count


# 1277. Count Square Submatrices with All Ones

def make_partial (m, n, matrix):
    ans = [[0 for __ in range (n + 1)] for _ in range (m + 1)]
    for i in range (m + 1):
        for j in range (n + 1):
            if i == 0 and j == 0:
                p = 0
            else:
                p = matrix[i-1][j-1] + ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1]
            ans[i][j] = p
    return ans

def get_rect (partial, i0, j0, i1, j1):
    return partial[i1][j1] + partial[i0][j0] - partial[i0][j1] - partial[i1][j0]

def count_squares (matrix):
    m, n = len (matrix), len (matrix[0])
    partial = make_partial (m, n, matrix)

    ans = 0
    for i in range (0, m):
        for j in range (0, n):
            max_w = min (m - i, n - j)
            for w in range (1, max_w + 1):
                if get_rect (partial, i, j, i+w, j+w) == w**2:
                    ans += 1
                else:
                    break

    return ans

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        return count_squares(matrix)

class Solution:
    def dobra(self,x,i,j,red_matrice):
        for k in range(i, i+red_matrice):
            for l in range(j, j+red_matrice):
                if x[k][l] == 0:
                    return False
        return True
        
        
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        res = 0
        
        for i in range(m):
            for j in range(n):
                for red_matrice in range(1, min(m,n)+1):
                    if i+red_matrice<=m and j+red_matrice<=n:
                        if self.dobra(matrix,i,j,red_matrice):
                            res += 1          
                        else:
                            break
        return res

import copy
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
      #running sum first
      matrix2 = copy.deepcopy(matrix)
      for i in range(len(matrix)):
        start = matrix[i][0]
        for j in range(1, len(matrix[0])):
          start += matrix[i][j]
          matrix2[i][j] = start
      for j in range(len(matrix[0])):
        start = matrix2[0][j]
        for i in range(1, len(matrix)):
          start += matrix2[i][j]
          matrix2[i][j] = start
      #print (matrix)
      res = 0
      row = len(matrix)
      col = len(matrix[0])
      for i in range(len(matrix)):
        for j in range(len(matrix[0])):
          if (matrix[i][j] == 1):
            possible = min(row - i, col-j)
            for t in range(possible):
              length = t+1
              sums = matrix2[i+t][j+t]
              if i - 1 >= 0: sums -= matrix2[i-1][j+t]
              if j - 1 >= 0: sums -= matrix2[i+t][j-1]
              if j - 1 >= 0 and i - 1 >= 0: sums += matrix2[i-1][j-1]
              #print (i,j,length,sums,res)
              if sums == length*length: res += 1
              else: break
      return res

from collections import defaultdict
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        num_right = defaultdict(lambda: 0)
        num_below = defaultdict(lambda: 0)
        m = len(matrix)
        n = len(matrix[0])
        
        for i in reversed(range(m)):
            for j in reversed(range(n)):
                if j+1 < n:
                    num_right[(i,j)] = num_right[(i, j+1)] + 1 if matrix[i][j+1] == 1 else num_right[(i, j+1)]
                else:
                    num_right[(i,j)] = 0
                if i+1 < m:
                    num_below[(i,j)] = num_below[(i+1, j)] + 1 if matrix[i+1][j] == 1 else num_below[(i+1, j)]
                else:
                    num_below[(i,j)] = 0
                
        count = defaultdict(lambda: 0)
        partial = defaultdict(lambda: 0)
        for i in reversed(range(m)):
            for j in reversed(range(n)):
                if matrix[i][j] == 0:
                    continue
                r = num_right[(i,j)]
                d = num_below[(i,j)]
                # print('******************')
                # print('Index', i,j)
                # print('Counts', r,d)
                # print(count)
                # print(partial)
                if matrix[i][j] == 1:
                    partial[(i,j,1)] = 1
                    count[1] += 1
                diff = min(r,d)
                flag = True
                for k in range(2, diff+2):
                    #print('Checking k=', k)
                    if partial[(i, j+1, k-1)] == 1 and partial[(i+1, j+1, k-1)] == 1 and partial[(i+1, j, k-1)] == 1:
                        partial[(i,j,k)] = 1
                        count[k] += 1
                    else:
                        flag = False
                    if not flag:
                        break
                    
        #print(count)
        return sum(count.values())        

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if(len(matrix)>0):
            t = [[0 for i in range(len(matrix[0])+1)] for j in range(len(matrix)+1)]
            result = 0
            for i in range(1,len(matrix)+1):
                for j in range(1, len(matrix[0])+1):
                    if(matrix[i-1][j-1] == 0):
                        t[i][j] == 0
                    else:
                        t[i][j] = min(t[i-1][j], t[i][j-1], t[i-1][j-1]) + 1
                        result += t[i][j]
            for i in t:
                print(i)
            return result
        else:
            # print(\"Ji\")
            return 0

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        import copy
        def grow_sqaure(x, y):
            oriX = copy.copy(x)
            oriY = copy.copy(y)
            
            count = 0
            if matrix[x][y] == 1:
                still_square = True
            while x < len(matrix) and y < len(matrix[0]) :
                for i in range(oriX, x+1):
                    if matrix[i][y] != 1:
                        return count

                for i in range(oriY, y+1):
                    if matrix[x][i] != 1:
                        return count
                count += 1
                x += 1
                y += 1
            return count

        count = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):

                count += grow_sqaure(i, j)
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        num_squares = 0
        for y in range(len(matrix)):
            for x in range(len(matrix[0])):
                num_squares += squaresAt(x,y, matrix)
        return num_squares
    
def squaresAt(x: int, y: int, matrix: List[List[int]]) -> int:
    
    size = 0
    
    while True:
        
        if y + size >= len(matrix): break
        if x + size >= len(matrix[0]): break
        
        good_row = checkRow(x, x+size, y+size, matrix)
        good_col = checkCol(x+size, y, y+size, matrix)
        
        if good_row and good_col: size += 1
        else: break
            
    return size
            
def checkRow(x1: int, x2: int, y: int, matrix: List[List[int]]) -> bool:  
    for x in range(x1, x2+1):
        if matrix[y][x] == 0: return False
    return True

def checkCol(x: int, y1: int, y2: int, matrix: List[List[int]]) -> bool:
    
    for y in range(y1, y2+1):
        if matrix[y][x] == 0: return False
    return True


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m=len(matrix)
        n=len(matrix[0])
        dp=[]
        for i in range(m):
            temp=[0]*n
            dp.append(temp)
        for j in range(n):
            if(matrix[0][j]==1):
                dp[0][j]=1
        for i in range(1,m,1):
            if(matrix[i][0]==1):
                dp[i][0]=1
        for i in range(1,m,1):
            for j in range(1,n,1):
                if(matrix[i][j]==1):
                    dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1
        ans=0
        for k in range(m):
            for l in range(n):
                ans+=dp[k][l]
        return ans
                


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        res = [[0 for _ in range(1+len(matrix[0]))] for _ in range(1+len(matrix))]
        s = 0
        m = 0
        for i in range(1,len(res)):
            for j in range(1,len(res[i])):
                
                if matrix[i-1][j-1] == 1:
                    res[i][j] = 1 + min(res[i-1][j],res[i][j-1],res[i-1][j-1])
                else :
                    res[i][j] = 0
                    
                s+= res[i][j]
                m = res[i][j] if res[i][j] > m else m
                    
        # for x in res:
        #     print(x)
        
        
        # ########### To Find Max Square Matrix size ################### 
        # print(m)
        # return m
            
        return s


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        M = len(matrix)
        N = len(matrix[0])
        
        ans = 0
        for i in range(M):
            for j in range(N):
                if matrix[i][j] > 0 and i>0 and j>0:
                    cand = min(matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1])
                    matrix[i][j] = (cand + 1)
                ans += matrix[i][j]
        return ans

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        rows=len(matrix)
        cols=len(matrix[0])
        res=0
        
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j]:
                    if i==0 or j==0:
                        res+=1
                    else:
                        temp=min(matrix[i][j-1],matrix[i-1][j-1],matrix[i-1][j])+1
                        res+=temp
                        matrix[i][j]=temp
                        
        return res
                    


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        answer = 0
        
        for r in range(len(matrix)) :
            for c in range(len(matrix[0])) :
                if r > 0 and c > 0 and matrix[r][c] > 0 : 
                    matrix[r][c] = min(matrix[r][c-1],matrix[r-1][c],matrix[r-1][c-1]) + 1
                answer += matrix[r][c]
            
        return answer
                    
                    


from collections import defaultdict
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        num_right = defaultdict(lambda: 0)
        num_below = defaultdict(lambda: 0)
        m = len(matrix)
        n = len(matrix[0])
        
        for i in reversed(range(m)):
            for j in reversed(range(n)):
                if j+1 < n:
                    num_right[(i,j)] = num_right[(i, j+1)] + 1 if matrix[i][j+1] == 1 else num_right[(i, j+1)]
                else:
                    num_right[(i,j)] = 0
                if i+1 < m:
                    num_below[(i,j)] = num_below[(i+1, j)] + 1 if matrix[i+1][j] == 1 else num_below[(i+1, j)]
                else:
                    num_below[(i,j)] = 0
                
        count = defaultdict(lambda: 0)
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    continue
                count[1] += 1
                r = num_right[(i,j)]
                d = num_below[(i,j)]
                # print('******************')
                # print('Index', i,j)
                # print('Counts', r,d)
                # print(count)
                curr = set()
                if r == 0 and d == 0:
                    continue
                flag = True
                for k in range(2,min(r,d)+2):
                    #print('Checking k=',k)
                    for x in range(i, i+k):
                        for y in range(j, j+k):
                            curr.add(matrix[x][y])
                            if matrix[x][y] == 0:
                                flag = False
                            if not flag:
                                break
                        if not flag:
                            break
                    if 0 not in curr and flag:
                        count[k] += 1
                    else:
                        break
        print(count)
        return sum(count.values())        

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix: return 0
        M, N = len(matrix), len(matrix[0])
        if M == 1 or N == 1: return 1
        for m in range(1, M):
            for n in range(1, N):
                if matrix[m][n] == 1:
                    if matrix[m-1][n] == matrix[m][n-1] == matrix[m-1][n-1]:
                        matrix[m][n] = matrix[m-1][n-1] + 1
                    else:
                        matrix[m][n] = max(min(matrix[m-1][n], matrix[m][n-1], matrix[m-1][n-1])+1, matrix[m][n]);
                
        return sum(sum(matrix, []))


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        import copy
        def grow_sqaure(x, y):
            oriX = copy.copy(x)
            oriY = copy.copy(y)
            still_square = False
            count = 0
            if matrix[x][y] == 1:
                still_square = True
            while x < len(matrix) and y < len(matrix[0]) and still_square:
                for i in range(oriX, x+1):
                    for j in range(oriY, y+1):
                        # print(oriX,oriY, x, y)
                        if matrix[i][j] != 1:
                            still_square = False
                            return count
                count += 1
                # print(oriX,oriY,x, y, \"this was a square\")
                x += 1
                y += 1
            return count

        count = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):

                count += grow_sqaure(i, j)
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        # For every possible size (min(height, length))
            # For every location of a 1
                # Check if all 1's (if the remaining array sizes are valid i.e i + size < len(matrix) and j + size < len(matrix[0]))
                
                # On the next size check, only continue if the previous step found at least 4. 
        # Error Checking
        if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        
        # General Case
        height = len(matrix)
        length = len(matrix[0])
        one_locations, square_submatrices = self.get_one_locations(matrix)
        
        current_count = 0
        for size in range(2, min(height, length) + 1):
            if size != 2 and current_count < 4:
                return square_submatrices
            
            # Reset the count
            current_count = 0
            
            for location in one_locations:
                # Check if it can even be valid before searching
                h = location[0]
                l = location[1]

                if (h + size - 1) < len(matrix) and (l + size - 1) < len(matrix[0]):
                    if self.check_all_ones(matrix, h, l, size):
                        current_count += 1    
                        
            square_submatrices += current_count
                
        return square_submatrices
                
    def check_all_ones(self, matrix, height, length, square_size):
        for i in range(height, height + square_size):
            for j in range(length, length + square_size):
                if matrix[i][j] != 1:
                    return False
                
        return True
                
    def get_one_locations(self, matrix):
        one_locations = set()
        one_count = 0
        
        for i, j in enumerate(matrix):
            for m, n in enumerate(matrix[i]):
                if n == 1:
                    one_locations.add((i,m))
                    one_count += 1
                    
        return one_locations, one_count

                
                
                
                
                
                


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        nrows = len(matrix)
        ncols = len(matrix[0])
        mainDict = {\"numBelow\":0,\"numRight\":0}
        test = [[None for i in range(ncols)] for j in range(nrows)]
        for r in reversed(range(nrows)):
            for c in reversed(range(ncols)):
                if r == nrows-1 and c== ncols-1:
                    if matrix[r][c]:
                        temp = {\"numBelow\":1,\"numRight\":1}
                        test[r][c] = temp
                    else:
                        test[r][c] = mainDict
                    continue
                elif r == nrows-1:
                    if matrix[r][c]:
                        numRight = test[r][c+1][\"numRight\"]+1
                        temp = {\"numBelow\":1,\"numRight\":numRight}
                        test[r][c] = temp
                    else:
                        test[r][c] = mainDict
                    continue
                elif c == ncols-1:
                    if matrix[r][c]:
                        numBelow = test[r+1][c][\"numBelow\"]+1
                        temp = {\"numBelow\":numBelow,\"numRight\":1}
                        test[r][c] = temp
                    else:
                        test[r][c] = mainDict
                else:
                    if matrix[r][c]:
                        currNumRight = test[r][c+1][\"numRight\"]+1
                        numBelow = test[r+1][c][\"numBelow\"]+1
                        temp = {\"numBelow\":numBelow,\"numRight\":currNumRight}
                        test[r][c] = temp
                    else:
                        test[r][c] = mainDict
        
        count = 0
        for r in range(nrows):
            for c in range(ncols):
                if matrix[r][c]:
                    print(r,c)
                    numRight = test[r][c][\"numRight\"]
                    numBelow = test[r][c][\"numBelow\"]
                    minCount = min(numRight,numBelow)
                    
                    temp = 0
                    for i in reversed(range(minCount)):
                        check = True
                        for j in range(i+1):
                            if test[r+j][c][\"numRight\"]>=(i+1):
                                continue
                            else:
                                check = False
                                break
                        if check:
                            break
                    if (i+1)>1:
                        count+=(i+1)
                    else:
                        count+=1
                    
                    
        return count                
#[
# [0,1,1,1],
# [1,1,0,1],
# [1,1,1,1],
# [1,0,1,0]]

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        hori = [row[:] for row in matrix]
        vert = [row[:] for row in matrix]
        R = len(matrix)
        C = len(matrix[0])
        for i in range(R):
            s = 0
            for j in range(C):
                if matrix[i][j]:
                    s += matrix[i][j]
                else:
                    s = 0
                hori[i][j] = s
        for j in range(C):
            s = 0
            for i in range(R):
                if matrix[i][j]:
                    s += matrix[i][j]
                else:
                    s = 0
                vert[i][j] = s
        out = 0
        #print(hori)
        #print(vert)
        for i in range(R):
            for j in range(C):
                if matrix[i][j] == 1:
                    if i-1<0 or j-1<0:
                        out+=1
                        continue
                    if matrix[i-1][j-1] == 0:
                        out +=1
                        continue
                    x = int(matrix[i-1][j-1]**0.5)
                    a = min([x, hori[i][j-1], vert[i-1][j]])
                    out += a+1
                    #print(i,j, out)
                    matrix[i][j] = (a+1)**2
        #print(matrix)
        return out

class Solution:
    def gs(self,matrix,x,y,i,j):
        ans = matrix[i][j]
        if y:
            ans -= matrix[i][y-1]
        if x:
            ans -= matrix[x-1][j]
        if x and y:
            ans += matrix[x-1][y-1]
        return ans
    
    def countSquares(self, matrix: List[List[int]]) -> int:
        n:int  = len(matrix)
        m = 0
        m = len(matrix[0])
        for i in range(n):
            pre = 0
            for j in range(m):
                matrix[i][j] += pre
                pre = matrix[i][j]
        for i in range(1,n):
            for j in range(m):
                matrix[i][j] += matrix[i-1][j]
            # print(matrix[i])
        ans = 0
        for i in range(n):
            for j in range(m):
                x,y = i,j
                l = 1
                while x >= 0 and y >=0:
                    # print(x,y,i,j,self.gs(matrix,x,y,i,j))
                    if l*l == self.gs(matrix,x,y,i,j):
                        ans+=1
                    else:
                        break
                    x,y,l = x-1,y-1,l+1
        return ans


from collections import defaultdict
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        res = 0
        for i in range(len(matrix)):
            res += matrix[i][0]
        
        for j in range(1,len(matrix[0])):
            res += matrix[0][j]
        
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                matrix[i][j] *= min(matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j]) + 1
                res += matrix[i][j]
        print(matrix)
        return res
        
            


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        # compute prefix square
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                re = 0
                if i > 0:
                    re += matrix[i - 1][j]
                if j > 0:
                    re += matrix[i][j - 1]
                if i > 0 and j > 0:
                    re -= matrix[i - 1][j - 1]
                matrix[i][j] += re
        print(matrix)
        # correct
        
        re = 0
        
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                # start matching squares at i j
                l = 0
                while i + l < len(matrix) and j + l < len(matrix[0]):
                    # check
                    # compute a sum area
                    tmp = matrix[i + l][j + l]
                    if j > 0:
                        tmp -= matrix[i + l][j - 1]
                    if i > 0:
                        tmp -= matrix[i - 1][j + l]
                    if i > 0 and j > 0:
                        tmp += matrix[i - 1][j - 1]
                    # print('{} {} {} {}'.format(i, j, l, tmp))
                    
                    if tmp != (l + 1) ** 2:
                        break
                    else:
                        re += 1
                    l += 1
        return re
                    
                
                


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        m = len(matrix)
        n = len(matrix[0])
        
        @functools.lru_cache(None)
        def dp(i, j):
            
            if matrix[i][j]:
                if 0 < i and 0 < j:
                    return min(dp(i-1, j-1), dp(i-1, j), dp(i, j-1)) + 1
                return 1
            return 0
        
        return sum([dp(i, j) for i in range(m) for j in range(n)])

from copy import deepcopy
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if matrix == [] or matrix[0] == []:
            return 0
        n, m = len(matrix), len(matrix[0])
        left = deepcopy(matrix)
        down = deepcopy(matrix)
        output = deepcopy(matrix)
        for i in reversed(list(range(n-1))):
            for j in reversed(list(range(m-1))):
                if matrix[i][j] == 1:
                    left[i][j] = left[i][j+1] + 1
                    down[i][j] = down[i+1][j] + 1
                    output[i][j] = min(left[i][j], down[i][j], output[i+1][j+1]+1)
                #print(i, j, output[i][j], left[i][j], down[i][j])
        return sum(sum(x) for x in output)


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        import copy
        if not matrix: return 0
        
        dp = copy.deepcopy(matrix)
        
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if matrix[i][j] == 1:
                    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
        
        total = 0
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                total += dp[i][j]
                    
        return total

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        for i in range(1, m):
            for j in range(1, n):
                matrix[i][j] *= min(matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j]) + 1
        return sum(map(sum, matrix))

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp = []
        count = 0
        for i in range(len(matrix)):
            inner = []
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    inner.append(0)
                else:
                    if i == 0 or j == 0:
                        inner.append(1)
                        count += 1
                    else:
                        c = 1 + min(dp[i-1][j], min(inner[j-1], dp[i-1][j-1]))
                        inner.append(c)
                        count += c
            dp.append(inner)
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        grid = matrix
        self.dp = [[[0,0] for j in grid[0]] for i in grid]
        dp = self.dp
        
        def ut(r,c):
            if r>=0 and c>=0:
                return self.dp[r][c][0]
            return 0
        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if r and c and grid[r][c]:
                    dp[r][c][1] = min ( dp[r][c-1][1], dp[r-1][c][1] , dp[r-1][c-1][1])
                    if dp[r][c][1] : dp[r][c][1] +=1
                    
                dp[r][c][1] = max(dp[r][c][1] , grid[r][c])
                dp[r][c][0] += dp[r][c][1]           
                    
                dp[r][c][0] += ut(r,c-1) + ut(r-1, c) - ut(r-1, c-1)
        print(dp)
                
        return dp[-1][-1][0]


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        def is_valid_square(start_row, end_row, start_col, end_col, matrix):
            # for row in range(start_row, end_row + 1):
            #     for col in range(start_col, end_col + 1):
            #         if matrix[row][col] != 1:
            #             return False    
            # return True
            
            return not any(matrix[row][col] == 0 for row in range(start_row, end_row + 1) for col in range(start_col, end_col + 1))
                
        result = 0
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                search_space_increase = 0
                while row + search_space_increase < len(matrix) and col + search_space_increase < len(matrix[0]):
                    if not is_valid_square(row, row + search_space_increase , col, col + search_space_increase, matrix):
                        break                        
                    result += 1
                    search_space_increase += 1
                        
        
        return result

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        dp = [[0 for x in range(n+1)] for l in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if matrix[i-1][j-1] != 0:
                    dp[i][j] = matrix[i-1][j-1] + min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
        return sum([sum(x) for x in dp])

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0]*(n+1) for _ in range(m+1)]
        res = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j]:
                    dp[i+1][j+1] = min(dp[i][j], dp[i][j+1], dp[i+1][j])+1
                res += dp[i+1][j+1]
        
        return res


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp=matrix
        r = len(dp)
        c = len(dp[0])
        ans=0
        for i in range(1,r):
            for j in range(1,c):
                if(dp[i][j]==0):
                    continue
                if(dp[i-1][j]!=0 and dp[i-1][j-1]!=0 and dp[i][j-1]!=0):
                    dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
        for i in dp:
            ans+=sum(i)
        return ans


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix); n = len(matrix[1])
        res = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j]:
                    if i == 0 or j == 0:
                        res += 1
                    else:
                        matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1],matrix[i-1][j-1])
                        res += matrix[i][j]
        return res


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        ansmatrix = [[0]*(m + 1) for _ in range(n+1)]
        count = 0
        
        for row in range(1, n + 1):
            for col in range(1, m + 1):
                if matrix[row - 1][col - 1] == 1:
                    ansmatrix[row][col] = 1 + min(ansmatrix[row][col - 1], ansmatrix[row - 1][col], ansmatrix[row - 1][col - 1])
                    count += ansmatrix[row][col]
                    
        return count


class Solution:
    def getsum(self,prefix,i,j):
        if i<0 or j <0:
            return 0
        else:
            return prefix[min(len(prefix),i)][min(len(prefix[0]),j)]
    def countSquares(self, matrix: List[List[int]]) -> int:
                
        m=len(matrix)
        n=len(matrix[0])
        dp=[]
        res=0
        for i in range(m):
            dp.append([0]*n)
        for i in range(m):
            if matrix[i][0]==1:
                dp[i][0]=1
                res=res+1
        for j in range(1,n):
            if matrix[0][j]==1:
                dp[0][j]=1
                res=res+1
                
        print(res)
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][j]>0:
                    dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1
                    res=res+dp[i][j]
        
        return res
                
        
        
        
       

        
#         m=len(matrix)
#         n=len(matrix[0])
#         sumv=[]
#         prefixsum=[]
#         for i in range(m):
#             sumv.append([0]*n)
#             prefixsum.append([0]*n)
        
#         for j in range(n):
#             sumv[0][j]=matrix[0][j]
            
#         for i in range(m):
#             for j in range(n):
#                 sumv[i][j]=matrix[i][j]+sumv[i-1][j]
 
        
#         for i in range(m):
#             prefixsum[i][0]=sumv[i][0]
            
            
#         for i in range(m):
#             for j in range(n):
#                 prefixsum[i][j]=sumv[i][j]+prefixsum[i][j-1]
                
 
        
#         res=0
        
#         for i in range(m):
#             for j in range(n):
#                 if matrix[i][j]!=0:
#                     for k in range(min(i,j)+2,0,-1):

#                         area=self.getsum(prefixsum,i,j)-self.getsum(prefixsum,i-k,j)-self.getsum(prefixsum,i,j-k)+self.getsum(prefixsum,i-k,j-k)

                        
#                         if k*k==area:
                            
#                             res+=k
#                             break
        # return res
                
        
        


class Solution:
    def getsum(self,prefix,i,j):
        if i<0 or j <0:
            return 0
        else:
            return prefix[min(len(prefix),i)][min(len(prefix[0]),j)]
    def countSquares(self, matrix: List[List[int]]) -> int:
                
        m=len(matrix)
        n=len(matrix[0])
        dp=[]
        res=0
        for i in range(m):
            dp.append([0]*n)
        for i in range(m):
            if matrix[i][0]==1:
                dp[i][0]=1
                res=res+1
        for j in range(1,n):
            if matrix[0][j]==1:
                dp[0][j]=1
                res=res+1
                
        print(res)
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][j]>0:
                    dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1
                    res=res+dp[i][j]
        print(dp)
        return res
                
        
        
        
       

        
#         m=len(matrix)
#         n=len(matrix[0])
#         sumv=[]
#         prefixsum=[]
#         for i in range(m):
#             sumv.append([0]*n)
#             prefixsum.append([0]*n)
        
#         for j in range(n):
#             sumv[0][j]=matrix[0][j]
            
#         for i in range(m):
#             for j in range(n):
#                 sumv[i][j]=matrix[i][j]+sumv[i-1][j]
 
        
#         for i in range(m):
#             prefixsum[i][0]=sumv[i][0]
            
            
#         for i in range(m):
#             for j in range(n):
#                 prefixsum[i][j]=sumv[i][j]+prefixsum[i][j-1]
                
 
        
#         res=0
        
#         for i in range(m):
#             for j in range(n):
#                 if matrix[i][j]!=0:
#                     for k in range(min(i,j)+2,0,-1):

#                         area=self.getsum(prefixsum,i,j)-self.getsum(prefixsum,i-k,j)-self.getsum(prefixsum,i,j-k)+self.getsum(prefixsum,i-k,j-k)

                        
#                         if k*k==area:
                            
#                             res+=k
#                             break
        # return res
                
        
        



class Solution:
    
    def countSquares(self, A):
        for i in range(1, len(A)):
            for j in range(1, len(A[0])):
                A[i][j] *= min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1]) + 1
        return sum(map(sum, A))

class Solution:
    def getsum(self,prefix,i,j):
        if i<0 or j <0:
            return 0
        else:
            return prefix[min(len(prefix),i)][min(len(prefix[0]),j)]
    def countSquares(self, matrix: List[List[int]]) -> int:
                
        m=len(matrix)
        n=len(matrix[0])
        dp=[]
        res=0
        for i in range(m):
            dp.append([0]*n)
        for i in range(m):
            if matrix[i][0]==1:
                dp[i][0]=1
                res=res+1
        for j in range(1,n):
            if matrix[0][j]==1:
                dp[0][j]=1
                res=res+1
                
        print(res)
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][j]>0:
                    dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1
                    res=res+dp[i][j]
        print(dp)
        return res
                
        
        
        
        for i in range(m):
            dp

        
#         m=len(matrix)
#         n=len(matrix[0])
#         sumv=[]
#         prefixsum=[]
#         for i in range(m):
#             sumv.append([0]*n)
#             prefixsum.append([0]*n)
        
#         for j in range(n):
#             sumv[0][j]=matrix[0][j]
            
#         for i in range(m):
#             for j in range(n):
#                 sumv[i][j]=matrix[i][j]+sumv[i-1][j]
 
        
#         for i in range(m):
#             prefixsum[i][0]=sumv[i][0]
            
            
#         for i in range(m):
#             for j in range(n):
#                 prefixsum[i][j]=sumv[i][j]+prefixsum[i][j-1]
                
 
        
#         res=0
        
#         for i in range(m):
#             for j in range(n):
#                 if matrix[i][j]!=0:
#                     for k in range(min(i,j)+2,0,-1):

#                         area=self.getsum(prefixsum,i,j)-self.getsum(prefixsum,i-k,j)-self.getsum(prefixsum,i,j-k)+self.getsum(prefixsum,i-k,j-k)

                        
#                         if k*k==area:
                            
#                             res+=k
#                             break
        # return res
                
        
        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                matrix[i][j] *= min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1
        return sum(map(sum, matrix))

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix) if matrix else 0, len(matrix[0]) if matrix else 0
        
        table = [[0]*n for _ in range(m)]
        ans = 0
        for i, j in product(list(range(m)), list(range(n))):
            if matrix[i][j] and j > 0 and i > 0:
                table[i][j] = min( table[i-1][j], table[i][j-1], table[i-1][j-1]) + 1
            else:
                table[i][j] = matrix[i][j]
                
            ans += table[i][j]
        
        return ans


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        #[0,1,1,1] 
        #[1,1,2,2]
        #[0,1,2,3] 15
        
        #leave the border as-is
        #using same matrix: O(1) space, O(nm) time
        for row in range(1,len(matrix)):
            for col in range(1, len(matrix[0])):
                if matrix[row][col] == 1: #if 0: ignore
                    ul = matrix[row-1][col-1]
                    u = matrix[row-1][col]
                    l = matrix[row][col-1]
                    val = min(ul, u, l) + 1
                    matrix[row][col] = val
        #print(matrix)
        total = 0
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                total += matrix[row][col]
        return total
        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m=len(matrix)
        n=len(matrix[0])
        ans=0
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][j]!=0 and matrix[i-1][j]!=0 and matrix[i][j-1]!=0 and matrix[i-1][j-1]!=0:
                    matrix[i][j]=min(matrix[i-1][j],matrix[i][j-1],matrix[i-1][j-1])+1
        for i in matrix:
            ans+=sum(i)
        return ans


class Solution:
      def countSquares(self, A):
        for i in range(1, len(A)):
            for j in range(1, len(A[0])):
                A[i][j] *= min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1]) + 1
        return sum(map(sum, A))

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        memo = [[0 for x in range(len(matrix[0]) + 1)] for y in range(len(matrix) + 1)]
        
        for i in range(1, len(memo)):
            for j in range(1, len(memo[0])):
                
                if matrix[i-1][j-1] == 0:
                    memo[i][j] = 0
                else:
                    memo[i][j] = min([memo[i-1][j-1], memo[i-1][j], memo[i][j-1]]) + 1
                
        tot = 0
        for i in range(len(memo)):
            for j in range(len(memo[0])):
                tot += memo[i][j]
                
        return tot


class Solution:
    def countSquares(self, A: List[List[int]]) -> int:
        for i in range(1, len(A)):
            for j in range(1, len(A[0])):
                A[i][j] *= min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1]) + 1
        return sum(map(sum, A))

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:        
        M=len(matrix)
        N=len(matrix[0])
        dp=[[0 for _ in range(N)]for _ in range(M)]
        res=0  
        for bottom in range(M):             
            for right in range(N):
                if bottom==0 or right==0:
                    dp[bottom][right]=1 if matrix[bottom][right]==1 else 0
                else:
                    dp[bottom][right]=min(dp[bottom-1][right-1],\\
                                          dp[bottom-1][right],\\
                                          dp[bottom][right-1])+1 \\
                                        if matrix[bottom][right]==1 else 0 
                res+=dp[bottom][right]

 
                
        return res
        

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                matrix[i][j] *= min(matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j]) + 1
        
        return sum(map(sum, matrix))

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        # dp(i, j) = number of squares that have bottom right corner at x1, y1
        
        m = len(matrix)
        n = len(matrix[0])
        dp = [[0 for i in range(n)] for j in range(m)]
        count = 0
        
        for i in range(m):
            for j in range(n):
                if i-1>=0 and j-1>=0 and matrix[i][j] == 1:
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
                elif matrix[i][j] == 1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
                count += dp[i][j]

        return count


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
          return 0
        res = 0
        M = len(matrix)
        N = len(matrix[0])
        for i in range(M):
          for j in range(N):
            if matrix[i][j] == 0:
              continue
            if i == 0 or j == 0:
              res += 1
            else:
              add = min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1])+1
              res += add
              matrix[i][j] = add
        return res
          


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])
        result = 0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 1:
                    idx = 1
                    isTrue = True
                    while isTrue and (r+idx) != rows and (c+idx) != cols:
                        for h in range(idx + 1):
                            if matrix[r + idx][c + h] != 1 or matrix[r + h][c + idx] != 1:
                                isTrue = False
                                break
                        if isTrue:
                            idx += 1
                    result += idx
        return result


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp = [[0 for i in range(len(matrix[0]) + 1)] for j in range(len(matrix) + 1)]
        total = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 1:
                    dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1], dp[i][j]) + 1
                    total += min(dp[i + 1][j], dp[i][j + 1], dp[i][j]) + 1
                
        return total


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if i > 0 and j > 0:
                    matrix[i][j] *= min(matrix[i-1][j], matrix[i-1][j-1], matrix[i][j-1])+1
                ans += matrix[i][j]
        return ans
    
    
    


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        max_y = len(matrix)
        max_x = len(matrix[0])
            
        for y in range(1,max_y):
            for x in range(1, max_x):
                if matrix[y][x] and matrix[y][x-1] and matrix[y-1][x] and matrix[y-1][x-1]:
                    matrix[y][x] = min(matrix[y][x-1], matrix[y-1][x], matrix[y-1][x-1]) + 1 
                   
        row_sums = [sum(row) for row in matrix]
        return sum(row_sums)

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        # dp(i, j) = number of squares that have bottom right corner at x1, y1
        
        m = len(matrix)
        n = len(matrix[0])
        dp = [[0 for i in range(n)] for j in range(m)]
        
        for i in range(m):
            for j in range(n):
                if i-1>=0 and j-1>=0 and matrix[i][j] == 1:
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
                elif matrix[i][j] == 1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
                        
        count = 0
        for i in range(m):
            for j in range(n):
                count += dp[i][j]
        
        return count


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if i > 0 and j > 0:
                    matrix[i][j] *= min(matrix[i-1][j], matrix[i-1][j-1], matrix[i][j-1])+1
                ans += matrix[i][j]
        return ans

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                matrix[i][j] = matrix[i][j] * (min({matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1]})+1)
        s = 0
        for i in matrix:
            s +=sum(i)
        return s


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        r,c = len(matrix),len(matrix[0])
        count = 0 
        for i in range(r):
            for j in range(c) :
                if matrix[i][j] == 1 :
                    if i == 0 or j == 0:
                        count += 1
                    else :
                        cell_val = min(matrix[i-1][j-1],matrix[i][j-1],matrix[i-1][j]) + matrix[i][j]
                        count += cell_val
                        matrix[i][j] = cell_val
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m,n = len(matrix), len(matrix[0])
        diag = 0
        square = [matrix[i][:] for i in range(m)]
        total = 0
        r, c = 0, 0
        while diag < m+n-1:
            if 0<r<m and 0<c<n and matrix[r][c]>0:
                square[r][c] += min(square[r][c-1], square[r-1][c], square[r-1][c-1])
            total += square[r][c]  
            r += 1
            c -= 1
            if (r>m-1) or (c<0):
                diag += 1
                r = 0 if diag<n else diag-n+1
                c = diag - r
        return total
                
                
                
                


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        def helper(x, y):
            temp = 0
            pre = [[x, y]]
            side = 1
            while True:
                flag = 1
                nxt = []
                for i in range(len(pre)):
                    a, b = pre[i]
                    if a + 1 >= len(matrix) or b + 1 >= len(matrix[0]) or matrix[a + 1][b + 1] != 1 or matrix[a + 1][b] != 1 or matrix[a][b + 1] != 1:
                        flag = 0
                        break
                    if i - side == -1:
                        nxt.append([a, b + 1])
                        nxt.append([a + 1, b + 1])
                        nxt.append([a + 1, b])
                    elif i - side >= 0:
                        nxt.append([a + 1, b])
                    else:
                        nxt.append([a, b + 1])
                if flag == 0:
                    break
                temp += 1
                side += 1
                pre = nxt
            return temp
            
        res = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    continue
                res += 1
                res += helper(i, j)
        return res


def checkCorners(row_size, col_size, r, c):
    
    if (0 <= r-1 < row_size and 0 <= c < col_size) and (0 <= r-1 < row_size and 0 <= c-1 < col_size) and (0 <= r < row_size and 0 <= c-1 < col_size):
        return True
    return False
    

class Solution:
    
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp = matrix[:]
        r_size = len(matrix)
        c_size = len(matrix[0])
        acc = 0
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if matrix[row][col] == 1 and checkCorners(r_size, c_size, row, col):
                    dp[row][col] += min(matrix[row][col - 1],
                                        matrix[row - 1][col],
                                        matrix[row - 1][col - 1])
                acc += dp[row][col]

        return acc
                        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if matrix==[]:
            return 0
        maxval=0
        for i in range(len(matrix[0])):
            if matrix[0][i]==1:
                maxval+=1
                
        for i in range(1,len(matrix)):
            if matrix[i][0]==1:
                maxval+=1
        print(maxval)
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                if matrix[i][j]:
                    
                    matrix[i][j]=min(matrix[i-1][j],matrix[i][j-1],matrix[i-1][j-1])+1
                    maxval+=matrix[i][j]
        for j in matrix:
            print((*j))
        return maxval
    
                    
               
       


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n, m = len(matrix), len(matrix[0])
        
        sub_sol = matrix[0][:]
        row, col = sub_sol[:], [0] * m
        
        squares = sum(sub_sol)
        for i in range(1, n):
            sol = []
            for j in range(m):
                val = matrix[i][j]
                if j == 0:
                    col.append(val)
                else:
                    if val == 0:
                        col.append(0)
                    else:
                        col.append(col[-1] + 1)
                
                if val == 0: row[j] = 0
                else: row[j] += 1
                    
                sol.append(min(col[-1], row[j], (1 + sub_sol[j - 1]) if j > 0 else 1))
            sub_sol = sol
            squares += sum(sub_sol)
            
        return squares
                    


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        def helper(x, y):
            temp = 0
            pre = [[x, y]]
            side = 1
            while True:
                flag = 1
                nxt = []
                for i in range(len(pre)):
                    a, b = pre[i]
                    if a + 1 >= len(matrix) or b + 1 >= len(matrix[0]) or matrix[a + 1][b + 1] != 1 or matrix[a + 1][b] != 1 or matrix[a][b + 1] != 1:
                        flag = 0
                        break
                    if i - side == -1:
                        nxt.append([a, b + 1])
                        nxt.append([a + 1, b + 1])
                        nxt.append([a + 1, b])
                    elif i - side >= 0:
                        nxt.append([a + 1, b])
                    else:
                        nxt.append([a, b + 1])
                if flag == 0:
                    break
                temp += 1
                side += 1
                pre = nxt
            return temp
            
        res = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    continue
                res += 1
                res += helper(i, j)
        return res

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        n = len(matrix)
        m = len(matrix[0])
        squares = 0
        for i in range(0, n):
            for j in range(0, m):
                if matrix[i][j] == 1:
                    squares += self.get_squares(matrix, i, j, n, m)
        
        return squares
    
    def get_squares(self, matrix, i, j, n, m):
        count = 1
        s = 2
        while i + s <= n and j + s <= m:
            all_ones = True
            for k in range(i, i + s):
                for l in range(j, j + s):
                    if matrix[k][l] == 0:
                        return count
            count += 1
            s += 1

        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m,n=len(matrix),len(matrix[0])
        ans=0
        for sx in range(m):
            for sy in range(n):
                if matrix[sx][sy]==1:
                    ans+=1
                    for by in range(sy+1,n):
                        if matrix[sx][by]==1 and sx+(by-sy)<m:
                            side=by-sy
                            all_one=True
                            for x in range(sx,sx+side+1):
                                if matrix[x][by]!=1:
                                    all_one=False
                                    break
                            if not all_one:
                                break
                            for y in range(sy,sy+side+1):
                                if matrix[sx+side][y]!=1:
                                    all_one=False
                                    break                                    
                            if all_one:
                                ans+=1
                                #print(sx,sy,side)
                            else:
                                break
                        else:
                            break
        return ans

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m,n = len(matrix), len(matrix[0])
        diag = 1
        square = [matrix[i][:] for i in range(m)]
        old_rec = [(0,0)] * m
        new_rec = [(0,0)] * m
        old_rec[0] = matrix[0][0], matrix[0][0]
        total = matrix[0][0]
        r, c = 0, 1
        while diag < m+n-1:
            if 0<=r<m and 0<=c<n:
                if matrix[r][c] == 0: 
                    new_rec[r] = 0,0
                elif r==0: 
                    new_rec[r] = (old_rec[r][0] + 1, 1)
                elif c==0:
                    new_rec[r] = (1, old_rec[r-1][1] + 1)
                else:
                    above_h = old_rec[r-1][1]
                    left_w = old_rec[r][0]
                    new_rec[r] = left_w + 1, above_h + 1
                    square[r][c] += min(left_w, above_h, square[r-1][c-1])
                total += square[r][c]
                
            r += 1
            c -= 1
            if (r>m) or (c<0): 
                new_rec, old_rec = old_rec, new_rec
                diag += 1
                r = 0 if diag<n else diag-n+1
                c = diag - r
        return total
                
                
                
                


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        squares = {1: set()}
        max_l = min(len(matrix), len(matrix[0]))
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]:
                    squares[1].add((i, j))
        
        for l in range(2, max_l+1):
            squares[l] = set()
            for s in squares[l-1]:
                right = (s[0]+1, s[1])
                down = (s[0], s[1]+1)
                down_right = (s[0]+1, s[1]+1)
                if right in squares[l-1] and down in squares[l-1] and down_right in squares[l-1]:
                    squares[l].add(s)
                    
        return sum([len(s) for s in squares.values()])

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        # 1 1 1
        # 1 2 2
        # 1 2 3
        R,C = len(matrix), len(matrix[0])
        dp = [[0 for i in range(C)]for j in range(R)]
        ans = 0
        for i in range(R):
            dp[i][0] = matrix[i][0]
            ans += dp[i][0]
        
        for j in range(C):
            dp[0][j] = matrix[0][j]
            ans += dp[0][j]
        
        for i in range(1,R):
            for j in range(1,C):
                if matrix[i][j] ==0:
                    dp[i][j] = 0
                else:
            
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                    ans += dp[i][j]
                    print(i,j,ans)
        #print(dp)
        return ans if dp[0][0] ==0 else ans-1

from typing import List

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        counts = [[0] * len(matrix[0]) for _ in range(len(matrix))]

        def get_val(r, c, m):
            if 0 <= r < len(m) and 0 <= c < len(m[0]):
                return m[r][c]
            return 0

        total = 0
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if matrix[r][c] == 1:
                    l = get_val(r, c-1, counts)
                    d = get_val(r-1, c-1, counts)
                    u = get_val(r-1, c, counts)
                    counts[r][c] = 1 + min(l, d, u)
                    total += counts[r][c]
        return total


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        M = len(matrix)
        N = len(matrix[0])
        
        dp = [[0 for _ in range(N)] for _ in range(M)]
        
        dp = matrix[:][:]
        
        for i in range(1,M):
            for j in range(1,N):
                if matrix[i][j]==1:
                    dp[i][j] = min([dp[i][j-1],dp[i-1][j],dp[i-1][j-1]])+1
                
        res = 0
        
        for i in range(M):
            for j in range(N):
                if dp[i][j]>0:
                    for size in range(1,dp[i][j]+1):
                        res+=1
                        
        print(dp)
                        
        return res


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        cnt = 0
        rows,cols = len(matrix),len(matrix[0])
        dp = [[0]*(cols+1) for i in range(rows+1)] # padding with 0
        for i in range(1,rows+1):
            for j in range(1,cols+1):
                if matrix[i-1][j-1] == 1:
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
                    cnt += dp[i][j]
        return cnt

        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        vertMemo = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        horizMemo = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        diagMemo = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        squareMemo = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        
        if matrix[0][0] == 1:
            vertMemo[0][0] = 1
            diagMemo[0][0] = 1
            horizMemo[0][0] = 1
            squareMemo[0][0] = 1
        
        for i in range(1, len(matrix[0])):
            if matrix[0][i] == 1:
                vertMemo[0][i] = 1
                diagMemo[0][i] = 1
                squareMemo[0][i] = 1
                horizMemo[0][i] = horizMemo[0][i-1] + 1
        
        for i in range(1, len(matrix)):
            if matrix[i][0] == 1:
                vertMemo[i][0] = vertMemo[i-1][0] + 1
                diagMemo[i][0] = 1
                squareMemo[i][0] = 1
                horizMemo[i][0] = 1
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                if matrix[i][j] == 1:
                    vertMemo[i][j] = vertMemo[i-1][j] + 1
                    horizMemo[i][j] = horizMemo[i][j-1] + 1
                    diagMemo[i][j] = diagMemo[i-1][j-1] + 1
                    squareMemo[i][j] = min(squareMemo[i-1][j-1]+1, vertMemo[i][j], horizMemo[i][j])
        #print(vertMemo)
        #print(horizMemo)
        #print(diagMemo)
        print(squareMemo)
        totSquares = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if squareMemo[i][j] != 0:
                    totSquares += squareMemo[i][j]
        return totSquares


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        n = len(matrix)
        m = len(matrix[0])
        memo = [[0]*m for i in range(n)]
        memo[0][0] = (matrix[0][0],matrix[0][0])
        for i in range(1,m):
            memo[0][i] = (memo[0][i-1][0] + matrix[0][i],matrix[0][i])
        for i in range(1,n):
            memo[i][0] = (memo[i-1][0][0] + matrix[i][0],matrix[i][0])
        for i in range(1,n):
            for j in range(1,m):
                # if matrix[i-1][j-1] == 0 or matrix[i][j] == 0:
                #     memo[i][j] = (memo[i-1][j][0] + memo[i][j-1][0] - memo[i-1][j-1][0] + matrix[i][j], matrix[i][j])
                # else:
                if matrix[i][j] == 0:
                    square_size = 0
                else:
                    square_size = min(memo[i-1][j][1],memo[i][j-1][1],memo[i-1][j-1][1])
                memo[i][j] = (memo[i-1][j][0] + memo[i][j-1][0] - memo[i-1][j-1][0] + (square_size+1)*matrix[i][j], square_size + matrix[i][j])
        return memo[-1][-1][0]
        
        


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        presum = [[0] * (len(matrix[0])+1) for _ in range(len(matrix)+1)]
        dp = [[0] * (len(matrix[0])+1) for _ in range(len(matrix)+1)]
        tot = 0
        for r in range(len(matrix)):
            cur_row = [0] * (len(matrix[0])+1)
            for c in range(len(matrix[0])):
                cur_row[c] = cur_row[c-1] + matrix[r][c]
                presum[r][c] = presum[r-1][c] + cur_row[c]
                if matrix[r][c] == 0:
                    dp[r][c] = 0
                else:
                    dp[r][c] = min(dp[r-1][c-1], dp[r-1][c], dp[r][c-1]) + 1
                    tot += dp[r][c]
                
        return tot

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        if m == 1 and n == 1:
            return matrix[0][0]
        
        count = [[[0]*3 for i in range(n+1)] for _ in range(m+1)]
        res = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if matrix[i-1][j-1]:
                    count[i][j][0] = count[i-1][j][0] + 1
                    count[i][j][1] = count[i][j-1][1] + 1
                    count[i][j][2] = min(count[i-1][j-1][2], count[i-1][j][0], count[i][j-1][1])+1
                    res += count[i][j][2]
        return res
                    


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    continue
                if matrix[i-1][j] > 0 and matrix[i][j-1] > 0 and matrix[i-1][j-1] > 0:
                    matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1])
        return sum([sum(v) for v in matrix])

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        M = len(matrix)
        N = len(matrix[0])
        
        dp = [[0 for _ in range(N)] for _ in range(M)]
        
        dp = matrix[:][:]
        
        for i in range(1,M):
            for j in range(1,N):
                if matrix[i][j]==1:
                    dp[i][j] = min([dp[i][j-1],dp[i-1][j],dp[i-1][j-1]])+1
                
        res = 0
        
        for i in range(M):
            for j in range(N):
                if dp[i][j]>0:
                    for size in range(1,dp[i][j]+1):
                        res+=1
                                        
        return res


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        
        count = 0
                
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                
                if i > 0 and j > 0 and matrix[i][j] > 0:                    
                    matrix[i][j] = min(matrix[i-1][j-1], min(matrix[i-1][j], matrix[i][j-1])) + 1
                
                if matrix[i][j] > 0:
                    count += matrix[i][j]
                    
                    
        return count
    

    
    


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        result = [matrix[0]]
        
        for i in range(1, len(matrix)):
            row = [matrix[i][0]]
            result.append(row)
            for j in range(1, len(matrix[i])):
                if not matrix[i][j]:
                    row.append(0)
                else:
                    row.append(1 + min(result[i-1][j], result[i][j-1], result[i-1][j-1]))
        return sum(sum(r) for r in result)

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp = copy.deepcopy(matrix)
        counter = 0
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i == 0 or j == 0 or dp[i][j] == 0:
                    counter += dp[i][j]
                    continue
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    counter += dp[i][j]
        
        return counter

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m,n = len(matrix), len(matrix[0])
        diag = 1
        square = [matrix[i][:] for i in range(m)]
        old_rec = [(0,0)] * m
        new_rec = [(0,0)] * m
        old_rec[0] = matrix[0][0], matrix[0][0]
        total = matrix[0][0]
        r, c = 0, 1
        while diag < m+n-1:
            if 0<=r<m and 0<=c<n:
                # print('r=', r, ' c=',c)
                if matrix[r][c] == 0: 
                    new_rec[r] = 0,0
                elif r==0: 
                    new_rec[r] = (old_rec[r][0] + 1, 1)
                elif c==0:
                    new_rec[r] = (1, old_rec[r-1][1] + 1)
                else:
                    above_h = old_rec[r-1][1]
                    left_w = old_rec[r][0]
                    # print(' left w=',left_w, 'above h=', above_h, ' sq=', square[r-1][c-1])
                    new_rec[r] = left_w + 1, above_h + 1
                    square[r][c] += min(left_w, above_h, square[r-1][c-1])
                total += square[r][c]
                # print(' number=',new_rec[r], ' total=', total )
                
            r += 1
            c -= 1
            if (r>m) or (c<0): 
                new_rec, old_rec = old_rec, new_rec
                diag += 1
                r = 0
                c = diag - r
        return total
                
                
                
                


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        c = 0
        dp = matrix
        for i in range(1, m):
            for j in range(1, n):
                if dp[i][j] != 0:
                    if dp[i-1][j] != 0 and dp[i-1][j-1] != 0 and dp[i][j-1] != 0:
                        dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])+1
        
        for i in dp:
            c+=sum(i)
        
        return c

class Solution:
\tdef countSquares(self, matrix: List[List[int]]) -> int:
\t\tfor r in range(len(matrix)):
\t\t\tfor c in range(len(matrix[0])):
\t\t\t\tif matrix[r][c] == 1:
\t\t\t\t\tif r == 0 or c == 0:
\t\t\t\t\t\tmatrix[r][c] = 1
\t\t\t\t\telse:
\t\t\t\t\t\tmatrix[r][c] = 1 + min(matrix[r - 1][c - 1], matrix[r - 1][c], matrix[r][c - 1])

\t\treturn sum(sum(matrix, []))


# 1277. Count Square Submatrices with All Ones

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        A = matrix
        for i in range(1, len(A)):
            for j in range(1, len(A[0])):
                A[i][j] *= min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1]) + 1
                
        # return sum(map(sum, A))
        return sum([A[i][j] for i in range(len(A)) for j in range(len(A[0]))])
    
# 1. class Solution:
# 2.     def countSquares(self, matrix: List[List[int]]) -> int:
# 3.         if matrix is None or len(matrix) == 0:
# 4.             return 0
# 5.         
# 6.         rows = len(matrix)
# 7.         cols = len(matrix[0])
# 8.         
# 9.         result = 0
# 10.         
# 11.         for r in range(rows):
# 12.             for c in range(cols):
# 13.                 if matrix[r][c] == 1:   
# 14.                     if r == 0 or c == 0: # Cases with first row or first col
# 15.                         result += 1      # The 1 cells are square on its own               
# 16.                     else:                # Other cells
# 17.                         cell_val = min(matrix[r-1][c-1], matrix[r][c-1], matrix[r-1][c]) + matrix[r][c]
# 18.                         result += cell_val
# 19.                         matrix[r][c] = cell_val #**memoize the updated result**
# 20.         return result  


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        def pref(x,y):
            return 0 if x<0 or y<0 else f[x][y]
        rows,cols = len(matrix),len(matrix[0]) if matrix else 0
        res = 0
        f = [[0 for j in range(cols)] for i in range(rows)]
        for i in range(rows):
            for j in range(cols):
                f[i][j] = 0 if matrix[i][j] == 0 else min(pref(i-1,j),pref(i,j-1),pref(i-1,j-1))+1
                res += f[i][j]
        #print(f)
        return res


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        '''
        f[i][j] = 以(i,j)为右下角的最大square边长
        '''
        row, col = len(matrix), len(matrix[0])
        f = [[0] * col for _ in range(row)]
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == 0: 
                    f[i][j] = 0
                    continue
                if i == 0 or j == 0:
                    f[i][j] = matrix[i][j]
                    continue
                
                f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1
      
        return sum([sum(f[i]) for i in range(row)])
                


class Solution:
    #
    # Solution 1: DP
    #
    def countSquares1(self, grid: List[List[int]]) -> int:
        n = len(grid); m = len(grid[0]) if grid else 0
        
        res = 0
        for r in range(n):
            for c in range(m):
                if grid[r][c] == 0: continue
                if r==0 or c==0: res += 1; continue
                grid[r][c] = min(grid[r-1][c-1], grid[r][c-1], grid[r-1][c]) + 1
                res += grid[r][c]
        return res
    
    #
    # Solution 2: Brute Force
    #
    def countSquares(self, grid):
        n = len(grid); m = len(grid[0]) if grid else 0
        
        def helper(sr, sc, k):
            res = 1
            for i in range(2, k+1):
                j = i-1
                er = sr + j 
                ec = sc + j
                for r in range(sr, er+1):
                    if r == er: 
                        if any(grid[r][c] == 0 for c in range(sc, sc+i)): return res
                    else: 
                        if grid[r][ec] == 0: return res
                res += 1
            return res
        
        res = 0
        for r in range(n):
            for c in range(m):
                if grid[r][c] == 0: continue
                res += helper(r, c, min(n-r, m-c))
        return res
    
\"\"\"
[[0,1,1,1],[1,1,1,1],[0,1,1,1]]
[[0,1,1,1],[1,1,0,1],[1,1,1,1],[1,0,1,0]]
\"\"\"    

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        
        MAXINT = 1 << 30
        
        most_recent_zero_to_left_or_here = [[None] * n for _ in range(m)]
        most_recent_zero_above_or_here = [[None] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    most_recent_zero_to_left_or_here[i][j] = j
                elif j == 0:
                    most_recent_zero_to_left_or_here[i][j] = -1
                else:
                    most_recent_zero_to_left_or_here[i][j] = most_recent_zero_to_left_or_here[i][j - 1]
                    
        for j in range(n):
            for i in range(m):
                if matrix[i][j] == 0:
                    most_recent_zero_above_or_here[i][j] = i
                elif i == 0:
                    most_recent_zero_above_or_here[i][j] = -1
                else:
                    most_recent_zero_above_or_here[i][j] = most_recent_zero_above_or_here[i - 1][j]
                    
        dp = [[0] * n for _ in range(m)]
        
        for i in range(m):
            dp[i][0] = matrix[i][0]
            
        for j in range(n):
            dp[0][j] = matrix[0][j]
            
        for i in range(1, m):
            for j in range(1, n):
                limit = min(i - most_recent_zero_above_or_here[i][j], j - most_recent_zero_to_left_or_here[i][j])
                old = dp[i - 1][j - 1]
                dp[i][j] = min(1 + old, limit)
                
        return sum(dp[i][j] for i in range(m) for j in range(n))


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        h, w = len(matrix), len(matrix[0])
        acc_mat, merge_status_mat = [[0]*w for _ in range(h)], [[0]*w for _ in range(h)]
        
        for i in range(h):
            for j in range(w):
                
                # check surounding value and status 
                if j-1 >=0:
                    left = acc_mat[i][j-1] 
                    left_status = merge_status_mat[i][j-1]
                else:
                    left = 0
                    left_status = 0 
                
                if i-1 >= 0:
                    top = acc_mat[i-1][j] 
                    top_status = merge_status_mat[i-1][j]
                else:
                    top = 0
                    top_status = 0 
                
                if  i-1>=0 and j-1>=0: 
                    topLeft = acc_mat[i-1][j-1]
                    topLeft_status = merge_status_mat[i-1][j-1]
                else:
                    topLeft = 0
                    topLeft_status = 0 
                
                # exec
                merge_status_mat[i][j] = min(topLeft_status, top_status, left_status) + 1 if matrix[i][j]  == 1 else 0
                # print(i, j, topLeft_status,   merge_status_mat[i-1][j], left_status, merge_status_mat)
                acc_mat[i][j] = left + top - topLeft + merge_status_mat[i][j]
                # print(left, top, topLeft, acc_mat)
            
        return acc_mat[i][j]


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        sq = 0
        m_row = range(len(matrix))
        m_col = range(len(matrix[0])) 
        
        def expand_square(row, n, m, p, square=0, count=1):
            while count > -1:
                for i in range(count):
                    if row + i == m:
                        return square
                    for j in range(count):
                        if n + j == p:
                            return square
                        elif matrix[row + i][n + j] != 1:
                            return square                
                square += 1
                count += 1
        
        for row in m_row:
            for n in m_col:
                if matrix[row][n] == 1:
                    sq += expand_square(row, n, len(matrix), len(matrix[0]))

                                    
        return sq

class Solution:
    #
    # Solution 1: DP
    #
    def countSquares1(self, grid: List[List[int]]) -> int:
        n = len(grid); m = len(grid[0]) if grid else 0
        
        res = 0
        for r in range(n):
            for c in range(m):
                if grid[r][c] == 0: continue
                if r==0 or c==0: res += 1; continue
                grid[r][c] = min(grid[r-1][c-1], grid[r][c-1], grid[r-1][c]) + 1
                res += grid[r][c]
        return res
    
    #
    # Solution 2: Brute Force
    #
    def countSquares(self, grid):
        n = len(grid); m = len(grid[0]) if grid else 0
        
        def helper(sr, sc, k):
            res = 1
            for i in range(2, k+1):
                j = i-1; er = sr+j; c = sc+j
                for r in range(sr, er+1):
                    if   r == er and any(grid[r][c] == 0 for c in range(sc, sc+i)): return res
                    elif r != er and     grid[r][c] == 0: return res
                res += 1
            return res
        
        res = 0
        for r in range(n):
            for c in range(m):
                if grid[r][c] == 0: continue
                res += helper(r, c, min(n-r, m-c))
        return res
    
\"\"\"
[[0,1,1,1],[1,1,1,1],[0,1,1,1]]
[[0,1,1,1],[1,1,0,1],[1,1,1,1],[1,0,1,0]]
\"\"\"    

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp=[[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        sum=0
        for i in range(len(dp[0])):
            dp[0][i]=matrix[0][i]
            sum+=dp[0][i]
        print(sum)
        for j in range(1,len(dp)):
            dp[j][0]=matrix[j][0]
            sum+=dp[j][0]
        print(sum)
        
        for i in range(1,len(dp)):
            for j in range(1,len(dp[0])):
                if matrix[i][j]==1:
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
                    sum+=dp[i][j]
        
        return sum
                    
    


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        mat = deepcopy(matrix)
        for i in range(0, len(mat)):
            for j in range(0, len(mat[0])):
                if mat[i][j] == 0:
                    continue
                if i - 1 >= 0:
                    top = mat[i - 1][j]
                else:
                    top = 0
                
                if j - 1 >= 0:
                    left = mat[i][j - 1]
                else:
                    left = -1
                    
                if i - 1 < 0 and j - 1 < 0:
                    top_left = -1
                else:
                    top_left = mat[i - 1][j - 1]
                
                if top_left > 0 and left > 0 and top > 0:
                    mat[i][j] = min(top_left, left, top) + 1
        ret = 0  
        for i in range(0, len(mat)):
            for j in range(0, len(mat[0])):
                ret += mat[i][j]
        return ret

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                matrix[i][j] *= min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1
        return sum(sum(row) for row in matrix)

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        count = 0
        m = len(matrix)
        n = len(matrix[0])
        
        def invalid_matrix(r, c, s):
            for i in range(0, s):
                for j in range(s):
                    if r + i >= m or c + j >= n:
                        return True
                    if r + i < m and c + j < n and matrix[r + i][c + j] == 0:
                        return True
                    
            return False
        
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    count += 1
                    size = 2
                    while True:
                        if invalid_matrix(i, j, size):
                            break
                        count += 1
                        size += 1
        
        return count
        


class Solution:
    
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        nrows = len(matrix)
        ncols = len(matrix[0])
        dp1 = [0] * ncols
        dp2 = [0] * ncols
        ans = 0
        for row in range(nrows):
            dp1, dp2 = dp2, [0] * ncols
            for col in range(ncols):
                if matrix[row][col] == 0:
                    continue
                if row == 0 or col == 0:
                    dp2[col] = 1
                else:
                    dp2[col] = 1 + min(dp1[col], dp1[col - 1], dp2[col - 1])
                ans += dp2[col]
        return ans

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                matrix[i][j] = (min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1) * matrix[i][j]
        
        res = sum([sum(r) for r in matrix])
        return res

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m,n, count = len(matrix), len(matrix[0]), 0
        size_matrix = [[0] * n for j in range(m)]
        indices = [(-1,-1), (-1,0), (0,-1)]
        
        def _in_range(i,j):
            return i>=0 and i<m and j>=0 and j<n
        
        for i in range(0,m):
            for j in range(0,n):
                if matrix[i][j] == 1:
                    if i == 0 or j == 0:
                        size_matrix[i][j] = matrix[i][j]
                        if matrix[i][j] == 1:
                            count += 1
                    else:
                        minimum = min([size_matrix[x+i][y+j] for x,y in indices if _in_range(x+i, y+j)])
                        size_matrix[i][j] = minimum + 1
                        count += 1 + minimum
        
        return count
                    
                    


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        max_square_size = min(m,n)
        ones = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    ones.append([i,j])
        # For each one check if there are squares
        square_count = len(ones)
        for p in ones:
            for j in range(1,max_square_size):
                
                #print(\"--\",p,j)
                found_zero = False
                for rj in range(j+1):
                    for cj in range(j+1):
                        try:
                            #print(j, p[0]+rj, p[1]+cj, matrix[p[0]+rj][p[1]+cj])
                            if matrix[p[0]+rj][p[1]+cj] == 0:
                                found_zero = True
                                break
                        except IndexError:
                            found_zero = True
                    if found_zero:
                        break
                #print(p,j,found_zero)
                if found_zero:
                    break
                else:
                    #print(p,j)
                    square_count += 1
                           
        return square_count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] != 1:
                    continue
                elif i == 0 or j == 0:
                    count += 1
                else:
                    matrix[i][j] = min(matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1]) + 1
                    count += matrix[i][j]
                
        return count

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp=matrix
        r = len(dp)
        c = len(dp[0])
        ans=0
        for i in range(1,r):
            for j in range(1,c):
                if(dp[i][j]==0):
                    continue
                if(dp[i-1][j]!=0 and dp[i-1][j-1]!=0 and dp[i][j-1]!=0):
                    dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
        print(dp)
        for i in dp:
            ans+=sum(i)
        return ans

import copy
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        m, n = len(matrix), len(matrix[0])
        
        counter = copy.deepcopy(matrix)
        

        for i in range(1,m):
            for j in range(1,n):
                
                if counter[i][j] == 1:
                    counter[i][j] = 1 + min(counter[i-1][j], counter[i-1][j-1],counter[i][j-1])
        
        total_count = 0
        
        for i in range(m):
            for j in range(n):
                total_count += counter[i][j] 
                    
        return total_count


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        
        
        rows = len(matrix)
        cols = len(matrix[0])
        count = 0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] and r > 0 and c > 0:
                    matrix[r][c] = min(matrix[r-1][c],matrix[r][c-1],matrix[r-1][c-1]) + 1
                count += matrix[r][c]
        return count
                    


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])
        
        def traverse_subsquares(i, j):
            max_size = min(i, j) + 1
            n_subsquares = 0
            for i_base in range(i, i - max_size, -1):
                size = i - i_base + 1
                # print(f\"---------- {i_base, size, max_size} -----------\")
                ip = i_base
                for jp in range(j, j - size, -1):
                    # print(ip, jp)
                    if not matrix[ip][jp]:
                        return n_subsquares
                for ip in range(i_base + 1, i_base + size, 1):
                    # print(ip, jp)
                    if not matrix[ip][jp]:
                        return n_subsquares
                n_subsquares += 1
                
            return n_subsquares
        
        # print(traverse_subsquares(2, 1))
        # print(\"&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&\")
        # print(traverse_subsquares(2, 1))
        # return
        
        total = 0
        for i in range(rows):
            for j in range(cols):
                n = traverse_subsquares(i, j)
                # print(f\"i={i}, j={j}, n={n}\")
                total += n
                
        return total

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])
        
        def traverse_subsquares(i, j):
            max_size = min(i, j) + 1
            n_subsquares = 0
            for i_base in range(i, i - max_size, -1):
                size = i - i_base + 1
                ip = i_base
                for jp in range(j, j - size, -1):
                    if not matrix[ip][jp]:
                        return n_subsquares
                for ip in range(i_base + 1, i_base + size, 1):
                    if not matrix[ip][jp]:
                        return n_subsquares
                n_subsquares += 1
                
            return n_subsquares
        
        total = 0
        for i in range(rows):
            for j in range(cols):
                n = traverse_subsquares(i, j)
                total += n
                
        return total

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        res = 0;
        rows, cols = len(matrix), len(matrix[0])
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 1 and r > 0 and c>0:
                    matrix[r][c] = min([matrix[r-1][c-1], matrix[r-1][c], matrix[r][c-1]]) + 1
                res += matrix[r][c]
        
        return res

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        rows = len(matrix)
        cols = len(matrix[0])
        ret = 0
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == 1:
                    if i == 0 or j == 0:
                        ret += 1
                    else:
                        min_side = min(matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1]) + 1
                        matrix[i][j] = min_side
                        ret += min_side
        return ret

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        ans = [[0]*(n+1) for _ in range(m+1)]
        
        count = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if matrix[i-1][j-1] == 1:
                    ans[i][j] = 1 + min(ans[i-1][j], ans[i-1][j-1], ans[i][j-1])
                    count += ans[i][j]
        return count
        
        # n = len(matrix)
        # m = len(matrix[0])
        # ans_matrix = [[0]*(m+1) for _ in range(n+1)]
        # print(ans_matrix)
        # count = 0
        # for i in range(1,n+1):
        #     for j in range(1, m+1):
        #         if matrix[i-1][j-1] == 1:
        #             ans_matrix[i][j] = min(ans_matrix[i][j-1], ans_matrix[i-1][j], ans_matrix[i-1][j-1]) + 1
        #             count += ans_matrix[i][j]
        # return count


class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        
        m, n = len(matrix), len(matrix[0])
        squares = copy.deepcopy(matrix)
        count = 0
        ones_in_col = [0] * n
        
        for row in range(m):
            ones_in_row = 0
            
            for col in range(n):
                ones_in_row = ones_in_row + 1 if matrix[row][col] else 0
                ones_in_col[col] = ones_in_col[col] + 1 if matrix[row][col] else 0
                top_left_res = 0 if row == 0 or col == 0 else squares[row - 1][col - 1]
                
                squares[row][col] = min(ones_in_row, ones_in_col[col], top_left_res + 1)
                # print('row', row, 'col', col, 'res', ones_in_row, ones_in_col[col], squares[row][col])

                count += squares[row][col]
        
        # print(squares)
        return count
            
    
    
'''
Brute-force: try all submatrices. O(n^2 * m^2)

0 1 1 1
1 1 1 1
0 1 1 1

0 1 2 3
1 2 3 4
0 1 2 3

0 1 1 1
1 2 2 2
0 3 3 3

first row:
get: 0 1 2 3






0 1 1 1 0
1 1 1 1 1
1 1 1 1 1
0 1 1 1 1
0 1 1 1 0

0 5 5 5 0
2 4 4 4 3
1 3 4 3 2
0 2 2 2 1
0 1 1 1 0

0 3 2 1 0
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
0 3 2 1 0

O(nm)



#         right = []
#         for row in matrix:
#             r = []
#             count = 0
#             for x in row:
#                 count = count + 1 if x else 0
#                 r.append(count)
#             right.append(r)

        
#         for row in range(m):
#             count = 0
#
#             for col in range(n):
#                 right[row][col] = count = count + 1 if matrix[row][col] else 0
            
#         for col in range(n):
#             count = 0
#
#             for row in range(m):
#                 bottom[row][col] = count = count + 1 if matrix[row][col] else 0

        # for row in range(m):
        #     for col in range(n):
        #         count += squares[row][col]
'''

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        res = 0
      
        @lru_cache(None)
        def search(i, j):
            nonlocal res 
            if i >= m or i < 0 or j >= n or j < 0:
                return 0
            
            val = (1 + min(search(i - 1, j), search(i, j - 1), search(i - 1, j - 1))) * matrix[i][j]
            res += val
            return val
        
        search(m - 1, n - 1)
        return res

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        sm = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i - 1 >= 0 and j - 1 >= 0 and matrix[i][j] > 0 and matrix[i][j - 1] > 0 and matrix[i - 1][j] > 0 and  matrix[i - 1][j - 1] > 0:
                    matrix[i][j] += min(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1])
                sm += matrix[i][j]
        return sm