1+ class Solution {
2+ public List <List <Integer >>pacificAtlantic (int [][]matrix ) {
3+ List <List <Integer >>result =new ArrayList <>();
4+ int row =matrix .length ;
5+ if (row ==0 )
6+ return result ;
7+ int col =matrix [0 ].length ;
8+ boolean [][]pacific =new boolean [row ][col ];
9+ boolean [][]atlantic =new boolean [row ][col ];
10+ // go through every single position in the first row
11+ for (int i =0 ;i <col ;i ++) {
12+ //run dfs on first row
13+ dfs (matrix ,0 ,i ,matrix [0 ][i ],pacific );
14+ //run dfs on last row
15+ dfs (matrix ,row -1 ,i ,matrix [row -1 ][i ],atlantic );
16+ }
17+ // get the position in most left column
18+ for (int i =0 ;i <row ;i ++) {
19+ dfs (matrix ,i ,0 ,matrix [i ][0 ],pacific );
20+ dfs (matrix ,i ,col -1 ,matrix [i ][col -1 ],atlantic );
21+ }
22+ for (int i =0 ;i <row ;i ++) {
23+ for (int j =0 ;j <col ;j ++) {
24+ // if the position is visited in both the Pacific and Atlantic oceans, we add to the result
25+ if (pacific [i ][j ] &&atlantic [i ][j ]) {
26+ List <Integer >currentResult =new ArrayList <>();
27+ currentResult .add (i );
28+ currentResult .add (j );
29+ result .add (currentResult );
30+ }
31+ }
32+ }
33+ return result ;
34+ }
35+
36+ public void dfs (int [][]matrix ,int r ,int c ,int preHeight ,boolean [][]visited ) {
37+ if (r <0 ||c <0 ||r >=matrix .length ||c >=matrix [0 ].length ||preHeight >matrix [r ][c ] ||visited [r ][c ])
38+ return ;
39+ visited [r ][c ] =true ;
40+ dfs (matrix ,r +1 ,c ,matrix [r ][c ],visited );
41+ dfs (matrix ,r -1 ,c ,matrix [r ][c ],visited );
42+ dfs (matrix ,r ,c +1 ,matrix [r ][c ],visited );
43+ dfs (matrix ,r ,c -1 ,matrix [r ][c ],visited );
44+ }
45+ }