diff options
Diffstat (limited to 'count_square_submatrices_ones.c')
-rw-r--r-- | count_square_submatrices_ones.c | 40 |
1 files changed, 15 insertions, 25 deletions
diff --git a/count_square_submatrices_ones.c b/count_square_submatrices_ones.c index c363997..a517ad1 100644 --- a/count_square_submatrices_ones.c +++ b/count_square_submatrices_ones.c @@ -7,34 +7,24 @@ */ 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() { 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); + 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); } |