# LeetCode 1277. Count Square Submatrices with All Ones

https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/

## 題目大意

給定元素只有 `0` 或 `1` 的 $m\times n$ 矩陣，有多少**子方陣**內容全為 `1`？

## 思考

這題感覺就用 DP 來解

令 $\text{dp}[i][j]$ 表示以 $(i, j)$ 為右下角的所有子方陣數量，包括大小為 $1 \times 1, 2 \times 2, \cdots \text{dp}[i][j] \times \text{dp}[i][j]$ 的方陣

$$
\text{dp}[i][j] = \begin{cases}
\text{matrix}[i][j] & \text{if } i = 0 \text{ or } j = 0 \\
\min(\text{dp}[i-1][j], \text{dp}[i][j-1], \text{dp}[i-1][j-1]) + 1 & \text{if } \text{matrix}[i][j] = 1 \\
0 & \text{if } \text{matrix}[i][j] = 0
\end{cases}
$$

每次計算出 $\text{dp}[i][j]$ 後，我們將其累加到 `ans` 中，即為所求

C++ 參考解答：

class Solution
{
public:
    int countSquares(vector<vector<int>> &matrix)
    {
        const int m = matrix.size();
        const int n = matrix.begin()->size();
        vector<vector<int>> dp(m, vector<int>(n));
        int ans = 0;

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (!(i && j))
                    dp[i][j] = matrix[i][j];
                else if (matrix[i][j] == 1)
                    dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;

                ans += dp[i][j];
            }
        }

        return ans;
    }
};

Go 參考解答：

func countSquares(matrix [][]int) int {
	m := len(matrix)
	n := len(matrix[0])

	dp := make([][]int, m)

	for j := range dp {
		dp[j] = make([]int, n)
	}

	var ans int

	for i := 0; i < m; i++ {
		if matrix[i][0] == 1 {
			dp[i][0] = 1
		}
	}

	for j := 0; j < n; j++ {
		if matrix[0][j] == 1 {
			dp[0][j] = 1
		}
	}

	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[i][j] == 1 {
				dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
			}
		}
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			ans += dp[i][j]
		}
	}

	return ans
}

func min(a, b, c int) int {
	if a < b && a < c {
		return a
	}
	if b < c {
		return b
	}
	return c
}