1+
2+
3+ /**
4+ * Return an array of arrays of size *returnSize.
5+ * The sizes of the arrays are returned as *returnColumnSizes array.
6+ * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
7+ */
8+
9+ int directions [4 ][2 ]= {{0 ,1 }, {0 ,-1 }, {1 ,0 }, {-1 ,0 }};
10+ bool pacific_reach [200 ][200 ];
11+ bool atlantic_reach [200 ][200 ];
12+
13+ void resetSet (bool set [200 ][200 ]) {
14+ for (int i = 0 ;i < 200 ;i ++ ) {
15+ for (int j = 0 ;j < 200 ;j ++ ) {
16+ set [i ][j ]= false;
17+ }
18+ }
19+ }
20+
21+ void dfs (int row ,int col ,bool set [200 ][200 ],int * * heights ,int rows ,int cols ) {
22+ set [row ][col ]= true;
23+ int a = 0 ;
24+ int b = 0 ;
25+ for (int i = 0 ;i < 4 ;i ++ ) {
26+ a = directions [i ][0 ]+ row ;
27+ b = directions [i ][1 ]+ col ;
28+ if ((a >=0 )&& (a < rows )&& (b >=0 )&& (b < cols )&& (!set [a ][b ])) {
29+ if (heights [a ][b ] >=heights [row ][col ]) {
30+ dfs (a ,b ,set ,heights ,rows ,cols );
31+ }
32+ }
33+ }
34+ }
35+
36+ int * * pacificAtlantic (int * * heights ,int heightsSize ,int * heightsColSize ,int * returnSize ,int * * returnColumnSizes ) {
37+
38+ int rows = heightsSize ;
39+ int cols = heightsColSize [0 ];
40+
41+ resetSet (pacific_reach );
42+ resetSet (atlantic_reach );
43+
44+ for (int row = 0 ;row < rows ;row ++ ) {
45+ dfs (row ,0 ,pacific_reach ,heights ,rows ,cols );
46+ dfs (row ,cols - 1 ,atlantic_reach ,heights ,rows ,cols );
47+ }
48+ for (int col = 0 ;col < cols ;col ++ ) {
49+ dfs (0 ,col ,pacific_reach ,heights ,rows ,cols );
50+ dfs (rows - 1 ,col ,atlantic_reach ,heights ,rows ,cols );
51+ }
52+
53+ int res = 0 ;
54+ for (int row = 0 ;row < rows ;row ++ ) {
55+ for (int col = 0 ;col < cols ;col ++ ) {
56+ if ((pacific_reach [row ][col ]== true)&& (atlantic_reach [row ][col ]== true)) {
57+ res += 1 ;
58+ }
59+ }
60+ }
61+
62+ * returnSize = res ;
63+ returnColumnSizes [0 ]= (int * )malloc (res * sizeof (int ));
64+ for (int i = 0 ;i < res ;i ++ ) {
65+ returnColumnSizes [0 ][i ]= 2 ;
66+ }
67+
68+ int * * results = (int * * )malloc (res * sizeof (int * ));
69+ res = 0 ;
70+ for (int row = 0 ;row < rows ;row ++ ) {
71+ for (int col = 0 ;col < cols ;col ++ ) {
72+ if ((pacific_reach [row ][col ]== true)&& (atlantic_reach [row ][col ]== true)) {
73+ int * buffer = (int * )malloc (2 * sizeof (int ));
74+ buffer [0 ]= row ;
75+ buffer [1 ]= col ;
76+ results [res ]= buffer ;
77+ res += 1 ;
78+ }
79+ }
80+ }
81+
82+ return results ;
83+ }