題目： LeetCode - 1277. Count Square Submatrices with All Ones

題目說明

給一個二維陣列，裡面包含 0 和 1，求出其中值為 1 的元素能組出幾個不同的正方形。

解題思路

對於陣列中的每個元素來說，若該值為 1，能組出的正方形個數為，左邊那個元素最多能組出的正方形個數、上面那個元素最多能組出的正方形個數 和 左上角那個元素最多能組出的正方形個數，三者的最小值 + 1，依照此想法做動態規劃即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int height = matrix.size(), width = matrix[0].size(), count = 0;
        for(int i = 0; i < height; ++i)
            for(int j = 0; j < width; ++j)
            {
                if(i != 0 && j != 0 && matrix[i][j] == 1)
                    matrix[i][j] += min({matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]});
                count += matrix[i][j];
            }
        return count;
    }
};