aboutsummaryrefslogtreecommitdiff
path: root/count_square_submatrices_ones.c
blob: a517ad1089576a1a72aed4d6db02a4437fd8f78f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 1277. Count Square Submatrices with All Ones
#include "leetcode.h"

/*
 * given an 'm * n' matrix of ones and zeros, return how many square submatrices
 * have all ones.
 */

int countSquares(int **matrix, int matrixSize, int *matrixColSize) {
  int ans = 0;
  for (int i = 0; i < matrixSize; ++i)
    for (int j = 0; j < matrixColSize[i]; ans += matrix[i][j++])
      if (matrix[i][j] && i && j)
        matrix[i][j] += fmin(matrix[i - 1][j - 1],
                             fmin(matrix[i - 1][j], matrix[i][j - 1]));
  return ans;
}

int main() {
  int m1i[3][4] = {{0, 1, 1, 1}, {1, 1, 1, 1}, {0, 1, 1, 1}},
      m2i[3][3] = {{1, 0, 1}, {1, 1, 0}, {1, 1, 0}};
  struct two_d_arr *m1 = two_d_arr_init(4, 3, m1i);
  struct two_d_arr *m2 = two_d_arr_init(3, 3, m2i);
  printf("%d\n",
         countSquares(m1->arr, m1->row_size, m2->col_size)); // expect: 15
  printf("%d\n",
         countSquares(m2->arr, m2->row_size, m2->col_size)); // expect: 7
  two_d_arr_free(m1);
  two_d_arr_free(m2);
}