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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
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
}
|