diff options
author | Jack Sangdahl <[email protected]> | 2025-01-18 21:04:01 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-18 21:04:01 -0700 |
commit | 9a3751a7bebaf2a138a3ec91cd38afc27dc54f6a (patch) | |
tree | 366af9fa4501d75b5896b6c614b99a697362367d /trapping_rain_water2.c | |
parent | 3a737ea8dc8304354f75257b3f796e507354ccdc (diff) | |
download | leetcode-9a3751a7bebaf2a138a3ec91cd38afc27dc54f6a.tar.gz leetcode-9a3751a7bebaf2a138a3ec91cd38afc27dc54f6a.zip |
407. trapping rain water 2
Diffstat (limited to 'trapping_rain_water2.c')
-rw-r--r-- | trapping_rain_water2.c | 95 |
1 files changed, 95 insertions, 0 deletions
diff --git a/trapping_rain_water2.c b/trapping_rain_water2.c new file mode 100644 index 0000000..adde260 --- /dev/null +++ b/trapping_rain_water2.c @@ -0,0 +1,95 @@ +// 407. Trapping Rain Water II +#include "leetcode.h" + +/* + * given an 'm x n' integer matrix 'heightMap' representing the height of each + * unit cell in a 2d elevation map, return the volume of water it can trap after + * raining + */ + +struct cell { + int x; + int y; + int h; +}; + +struct heap { + struct cell *cells; + int size; +}; + +struct heap *heap_create(int capacity) { + struct heap *heap = (struct heap *)malloc(sizeof(struct heap)); + heap->cells = (struct cell *)malloc(capacity * sizeof(struct cell)); + heap->size = 0; + return heap; +} + +void heap_push(struct heap *heap, int x, int y, int h) { + int i = heap->size++; + while (i && h < heap->cells[(i - 1) / 2].h) + heap->cells[i] = heap->cells[(i - 1) / 2], i = (i - 1) / 2; + heap->cells[i] = (struct cell){x, y, h}; +} + +struct cell heap_pop(struct heap *heap) { + struct cell root = heap->cells[0], prev = heap->cells[--heap->size]; + int i, child; + for (i = 0; (child = 2 * i + 1) < heap->size; i = child) { + if (child + 1 < heap->size && + heap->cells[child].h > heap->cells[child + 1].h) + child++; + if (prev.h <= heap->cells[child].h) + break; + heap->cells[i] = heap->cells[child]; + } + return heap->cells[i] = prev, root; +} + +int trapRainWater(int **heightMap, int heightMapSize, int *heightMapColSize) { + int m = heightMapSize, n = *heightMapColSize, water = 0, max_height = 0; + bool vis[m][n]; + if (m < 3 || n < 3) + return 0; + memset(vis, false, sizeof(vis)); + struct heap *heap = heap_create(m * n); + for (int i = 0; i < m; i++) + for (int j = 0; j < n; j++) + if (!i || i == m - 1 || !j || j == n - 1) { + heap_push(heap, i, j, heightMap[i][j]); + vis[i][j] = true; + } + int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; + while (heap->size) { + struct cell cell = heap_pop(heap); + max_height = cell.h > max_height ? cell.h : max_height; + for (int i = 0; i < 4; i++) { + int x = cell.x + dir[i][0], y = cell.y + dir[i][1]; + if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) { + vis[x][y] = true; + heightMap[x][y] < max_height ? (water += max_height - heightMap[x][y], + heap_push(heap, x, y, max_height)) + : heap_push(heap, x, y, heightMap[x][y]); + } + } + } + free(heap->cells); + free(heap); + return water; +} + +int main() { + int hm1i[3][6] = {{1, 4, 3, 1, 3, 2}, {3, 2, 1, 3, 2, 4}, {2, 3, 3, 2, 3, 1}}; + int hm2i[5][6] = {{3, 3, 3, 3, 3}, + {3, 2, 2, 2, 3}, + {3, 2, 1, 2, 3}, + {3, 2, 2, 2, 3}, + {3, 3, 3, 3, 3}}; + struct two_d_arr hm1, hm2, hm3; + two_d_arr_init(&hm1, ARRAY_SIZE(hm1i), ARRAY_SIZE(hm1i[0]), hm1i); + two_d_arr_init(&hm2, ARRAY_SIZE(hm2i), ARRAY_SIZE(hm2i[0]), hm2i); + printf("%d\n", + trapRainWater(hm1.arr, hm1.row_size, hm1.col_size)); // expect: 4 + printf("%d\n", + trapRainWater(hm2.arr, hm2.row_size, hm2.col_size)); // expect: 10 +} |