leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1277.cpp (881B)

      1 class Solution {
      2   public:
      3     int countSquares(const vector<vector<int>> &matrix) {
      4         int n = matrix.size(), m = matrix[0].size();
      5         vector<vector<int>> count(n + 1, vector<int>(m + 1));
      6 
      7         for (int i = 1; i <= n; i++) {
      8             for (int j = 1; j <= m; j++) {
      9                 count[i][j] = matrix[i - 1][j - 1] + count[i - 1][j] + count[i][j - 1] - count[i - 1][j - 1];
     10             }
     11         }
     12 
     13         int res = 0;
     14         for (int i = 1; i <= n; i++) {
     15             for (int j = 1; j <= m; j++) {
     16                 int x = i, y = j;
     17                 for (int k = 1, x = i, y = j; x <= n && y <= m; x++, y++, k++) {
     18                     int sum = count[x][y] - count[i - 1][y] - count[x][j - 1] + count[i - 1][j - 1];
     19                     if (sum != k * k) break;
     20                     res++;
     21                 }
     22             }
     23         }
     24 
     25         return res;
     26     }
     27 };