diff options
-rw-r--r-- | count_square_submatrices_ones.c | 40 | ||||
-rw-r--r-- | count_square_submatrices_ones.py | 26 |
2 files changed, 66 insertions, 0 deletions
diff --git a/count_square_submatrices_ones.c b/count_square_submatrices_ones.c new file mode 100644 index 0000000..c363997 --- /dev/null +++ b/count_square_submatrices_ones.c @@ -0,0 +1,40 @@ +// 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) { + if (!matrix || !matrixSize || !matrixColSize || !*matrixColSize) + return 0; + int rows = matrixSize, cols = *matrixColSize; + int dp[rows][cols]; + for (int i = 0; i < rows; i++) + dp[i][0] = matrix[i][0]; + for (int i = 0; i < cols; i++) + dp[0][i] = matrix[0][i]; + for (int i = 1; i < rows; i++) + for (int j = 1; j < rows; j++) + dp[i][j] = matrix[i][j] == 1 + ? fmin(dp[i - 1][j], fmin(dp[i][j - 1], dp[i - 1][j - 1])) + : 0; + int cnt = 0; + for (int i = 0; i < rows; i++) + for (int j = 0; j < cols; j++) + cnt += dp[i][j]; + return cnt; +} + +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, m2; + two_d_arr_init(&m1, 4, 3, m1i); + two_d_arr_init(&m2, 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); +} diff --git a/count_square_submatrices_ones.py b/count_square_submatrices_ones.py new file mode 100644 index 0000000..399a741 --- /dev/null +++ b/count_square_submatrices_ones.py @@ -0,0 +1,26 @@ +# 1277. Count Square Submatrices with All Ones + +""" +given an 'm * n' matrix of ones and zeros, return how many square submatrices +have all ones. +""" + + +class Solution(object): + def countSquares(self, matrix): + """ + :type matrix: List[List[int]] + :rtype: int + """ + for i in range(1, len(matrix)): + for j in range(1, len(matrix[0])): + matrix[i][j] *= ( + min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1 + ) + return sum(map(sum, matrix)) + + +if __name__ == "__main__": + obj = Solution() + print(obj.countSquares(matrix=[[0, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]])) + print(obj.countSquares(matrix=[[1, 0, 1], [1, 1, 0], [1, 1, 0]])) |