aboutsummaryrefslogtreecommitdiff
path: root/pacific_atlantic_water_flow.c
blob: 3797b5e390fc76e972da90208451529f2ea2a116 (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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// 417. Pacific Atlantic Water Flow
#include "leetcode.h"

/*
 * there is an 'm x n' rectangular island that bords both the pacific and
 * atlantic ocean. the pacific ocean touches the island's left and top edges,
 * and the atlantic ocean touches the islands right and bottom edges. the island
 * is partitioned into a grid of square cells. you are given an 'm x n' integer
 * matrix 'heights' where 'heights[r][c]' represents the height above sea level
 * of the cell at coordinate '(r, c)'. the island receives a lot of rain, and
 * the rain water can flow to neighbouring cells directly in any cardinal
 * direction. return a 2d list of grid coordinates 'result' where 'result[i] =
 * [r_i, c_i]' denotes that rain water can flow from cell '(r_i, c_i)' to both
 * the pacific and atlantic oceans.
 */

#define MASK 0x1FFFF
#define PACIFIC 0x40000000
#define ATLANTIC 0x20000000
#define BOTH 0x60000000

int check_inner(int **heights, int heightsSize, int heightsColSize, int type,
                int row, int col) {
  heights[row][col] |= type;
  int res = (heights[row][col] & BOTH) == BOTH;
  int val = heights[row][col] & MASK;
  if (row && !(heights[row - 1][col] & type) &&
      (heights[row - 1][col] & MASK) >= val)
    res +=
        check_inner(heights, heightsSize, heightsColSize, type, row - 1, col);
  if (col && !(heights[row][col - 1] & type) &&
      (heights[row][col - 1] & MASK) >= val)
    res +=
        check_inner(heights, heightsSize, heightsColSize, type, row, col - 1);
  if (col < heightsColSize && !(heights[row][col + 1] & type) &&
      (heights[row][col + 1] & MASK) >= val)
    res +=
        check_inner(heights, heightsSize, heightsColSize, type, row, col + 1);
  if (row < heightsSize && !(heights[row + 1][col] & type) &&
      (heights[row + 1][col] & MASK) >= val)
    res +=
        check_inner(heights, heightsSize, heightsColSize, type, row + 1, col);
  return res;
}

int **pacificAtlantic(int **heights, int heightsSize, int *heightsColSize,
                      int *returnSize, int **returnColumnSizes) {
  int n = heightsSize - 1, m = *heightsColSize - 1;
  for (int i = 0; i < m; i++)
    if (!(heights[0][i] & PACIFIC))
      check_inner(heights, n, m, PACIFIC, 0, i);
  for (int i = 1; i <= n; i++)
    if (!(heights[i][0] & PACIFIC))
      check_inner(heights, n, m, PACIFIC, i, 0);
  int res_size = 0;
  for (int i = 0; i <= m; i++)
    if (!(heights[n][i] & ATLANTIC))
      res_size += check_inner(heights, n, m, ATLANTIC, n, i);
  for (int i = 0; i < n; i++)
    if (!(heights[i][m] & ATLANTIC))
      res_size += check_inner(heights, n, m, ATLANTIC, i, m);
  *returnSize = res_size;
  *returnColumnSizes = (int *)malloc(res_size * sizeof(int));
  int **ans = (int **)malloc(res_size * sizeof(int *));
  res_size = 0;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= m; j++)
      if ((heights[i][j] & BOTH) == BOTH) {
        (*returnColumnSizes)[res_size] = 2;
        ans[res_size] = (int *)malloc(2 * sizeof(int));
        ans[res_size][0] = i;
        ans[res_size][1] = j;
        res_size++;
      }
  return ans;
}

int main() {
  int h1i[5][5] = {{1, 2, 2, 3, 5},
                   {3, 2, 3, 4, 4},
                   {2, 4, 5, 3, 1},
                   {6, 7, 1, 4, 5},
                   {5, 1, 1, 2, 4}},
      h2i[1][1] = {{1}};
  struct two_d_arr *h1 =
      two_d_arr_init(ARRAY_SIZE(h1i), ARRAY_SIZE(h1i[0]), h1i);
  struct two_d_arr *h2 =
      two_d_arr_init(ARRAY_SIZE(h2i), ARRAY_SIZE(h2i[0]), h2i);
  int rs1, *rcs1,
      **pa1 = pacificAtlantic(h1->arr, h1->row_size, h1->col_size, &rs1, &rcs1);
  int rs2, *rcs2,
      **pa2 = pacificAtlantic(h2->arr, h2->row_size, h2->col_size, &rs2, &rcs2);
  for (int i = 0; i < rs1; i++) {
    for (int j = 0; j < rcs1[i]; j++)
      printf("%d ",
             pa1[i][j]); // expect: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
    printf("\n");
  }
  for (int i = 0; i < rs2; i++) {
    for (int j = 0; j < rcs2[i]; j++)
      printf("%d ", pa2[i][j]); // expect: [[0,0]]
    printf("\n");
  }
  for (int i = 0; i < rs1; i++)
    free(pa1[i]);
  free(pa1);
  free(rcs1);
  for (int i = 0; i < rs2; i++)
    free(pa2[i]);
  free(pa2);
  free(rcs2);
}