diff options
author | Jack Sangdahl <[email protected]> | 2025-08-19 21:27:20 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-08-19 21:27:20 -0600 |
commit | 567f9c64e8224d9e3d899f81004adbb1db0c2b22 (patch) | |
tree | d590c9a96c26ce9f9e3c6c02b0df7535c8bbe4d9 | |
parent | 933b3b41aa8f2286e7f2f846925b45c8df15282d (diff) | |
download | leetcode-567f9c64e8224d9e3d899f81004adbb1db0c2b22.tar.gz leetcode-567f9c64e8224d9e3d899f81004adbb1db0c2b22.zip |
1277. count square submatricies with all ones
-rw-r--r-- | count_square_submatrices_ones.c | 25 | ||||
-rw-r--r-- | count_square_submatrices_ones.py | 2 |
2 files changed, 8 insertions, 19 deletions
diff --git a/count_square_submatrices_ones.c b/count_square_submatrices_ones.c index c363997..34c8d51 100644 --- a/count_square_submatrices_ones.c +++ b/count_square_submatrices_ones.c @@ -7,24 +7,13 @@ */ 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 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() { diff --git a/count_square_submatrices_ones.py b/count_square_submatrices_ones.py index 399a741..1ce43e7 100644 --- a/count_square_submatrices_ones.py +++ b/count_square_submatrices_ones.py @@ -14,7 +14,7 @@ class Solution(object): """ for i in range(1, len(matrix)): for j in range(1, len(matrix[0])): - matrix[i][j] *= ( + matrix[i][j] += ( min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1 ) return sum(map(sum, matrix)) |