# 【LeetCode】 1277. Count Square Submatrices with All Ones

## Description
> Given a `m * n` matrix of ones and zeros, return how many square submatrices have all ones.

> Constraints:
> * `1 <= arr.length <= 300`
> * `1 <= arr[0].length <= 300`
> * `0 <= arr[i][j] <= 1`

> 給予一個`m * n`且只有零和一的陣列，回傳裡面有多少用一組成的正方形。

> 限制：
> * `1 <= arr.length <= 300`
> * `1 <= arr[0].length <= 300`
> * `0 <= arr[i][j] <= 1`

## Example:

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.

## Solution

* 解題靈感來自[這題](https://hackmd.io/@Zero871015/LeetCode-221)。
* 上面那題是要求最大的正方形多大，其解法是用小的正方形慢慢堆成大的。因為大的正方形都包含了小的正方形的資訊，我們就可以直接透過總和得到答案。

### Code

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        if(matrix.empty())
            return 0;
        int sum = 0;
        for(int i = 0; i < matrix.size(); i++)
        {
            for(int j = 0; j < matrix[0].size(); j++)
            {
                if(i != 0 && j != 0 && matrix[i][j] == 1)
                    matrix[i][j] = min(min(matrix[i - 1][j], matrix[i][j - 1]), matrix[i - 1][j - 1]) + matrix[i][j];
                sum += matrix[i][j];
            }
        }
        return sum;
    }
};

###### tags: `LeetCode` `C++`