aboutsummaryrefslogtreecommitdiff
path: root/trapping_rain_water2.c
blob: adde2602ce667d853e6444a86c6bdf1c645b61c5 (plain)
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
}