【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

• 解題靈感來自這題。
• 上面那題是要求最大的正方形多大，其解法是用小的正方形慢慢堆成大的。因為大的正方形都包含了小的正方形的資訊，我們就可以直接透過總和得到答案。

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++