C++ easy understood solution | brute force enumeration of side length using prefix sum matrix
\nclass Solution {\npublic:\n    // brute force using prefix sum\n    int countSquares(vector<vector<int>>& matrix) {\n        int n = matrix.size(), m = matrix
```\nclass Solution {\npublic:\n    // brute force using prefix sum\n    int countSquares(vector<vector<int>>& matrix) {\n        int n = matrix.size(), m = matrix[0].size();\n        vector<vector<int>> ps(n + 1, vector<int>(m + 1));\n        // prefix sum matrix\n        for (int i = 1; i <= n; ++ i)\n            for (int j = 1; j <= m; ++ j)\n                ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j - 1];\n        int ans = 0;\n        // enum side from 1 to min(num_rows, nums_cols)\n        for (int s = 1; s <= min(n, m); ++ s)\n            for (int i = s; i <= n; ++ i)\n                for (int j = s; j <= m; ++ j)\n                    if (ps[i][j] - ps[i - s][j] - ps[i][j - s] + ps[i - s][j - s] == s * s) ++ ans;\n        return ans;\n    }\n};\n```
['Prefix Sum']