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

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures

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:
		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):
					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:

	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:
		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:
		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]
					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:
		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]
				elif 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
		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:
		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):
			if r < 0 or r >= rownum or c < 0 or (c >= colnum):
				return 0
			elif matrix[r][c] == 0:
				return 0
			elif 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
		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:
		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 not matrix:
			return 0
		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):
				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:
		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:
		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, 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, 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, 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:

	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]
				elif 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:
		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]
				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):
					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
		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:
		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


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:
		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
		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]
						if sums == length * length:
							res += 1
						else:
							break
		return res


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:
			return 0


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
		return s


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]
				curr = set()
				if r == 0 and d == 0:
					continue
				flag = True
				for k in range(2, min(r, d) + 2):
					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:
		if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:
			return 0
		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
			current_count = 0
			for location in one_locations:
				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:
		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
		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
					matrix[i][j] = (a + 1) ** 2
		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]
		ans = 0
		for i in range(n):
			for j in range(m):
				(x, y) = (i, j)
				l = 1
				while x >= 0 and y >= 0:
					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:
		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)
		re = 0
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				l = 0
				while i + l < len(matrix) and j + l < len(matrix[0]):
					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]
					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)
		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:
		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)
				elif 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):
			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:
		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


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:
		for row in range(1, len(matrix)):
			for col in range(1, len(matrix[0])):
				if matrix[row][col] == 1:
					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
		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:
		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, matrix: List[List[int]]) -> int:
		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:
		(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:
		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:
		(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)
				elif 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:
		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
							else:
								break
						else:
							break
		return ans


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:
		(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)
		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)]
		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(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:
		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:
		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:

		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]
		return res


class Solution:

	def countSquares(self, matrix: List[List[int]]) -> int:
		(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:

	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):
				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
				merge_status_mat[i][j] = min(topLeft_status, top_status, left_status) + 1 if matrix[i][j] == 1 else 0
				acc_mat[i][j] = left + top - topLeft + merge_status_mat[i][j]
		return acc_mat[i][j]


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:
		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:
		(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])
		square_count = len(ones)
		for p in ones:
			for j in range(1, max_square_size):
				found_zero = False
				for rj in range(j + 1):
					for cj in range(j + 1):
						try:
							if matrix[p[0] + rj][p[1] + cj] == 0:
								found_zero = True
								break
						except IndexError:
							found_zero = True
					if found_zero:
						break
				if found_zero:
					break
				else:
					square_count += 1
		return square_count


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
				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:
		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:
		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)
				count += squares[row][col]
		return count


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