Count Square Submatrices with All Ones（C++统计全为 1 的正方形子矩阵）

Bertha 。 2023-01-02 10:24 80阅读 0赞

解题思路：

（1）参考网址：[https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/644655/C%2B%2B-DP-Solution-Explaination-without-modifying-the-input-matrix][https_leetcode.com_problems_count-square-submatrices-with-all-ones_discuss_644655_C_2B_2B-DP-Solution-Explaination-without-modifying-the-input-matrix]

（2）当前位置(i,j)构成边长的大小和(i,j-1)，(i-1,j)，(i-1,j-1)构成的边长大小相关

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

[https_leetcode.com_problems_count-square-submatrices-with-all-ones_discuss_644655_C_2B_2B-DP-Solution-Explaination-without-modifying-the-input-matrix]: https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/644655/C%2B%2B-DP-Solution-Explaination-without-modifying-the-input-matrix