11package com .fishercoder .solutions ;
22
33import java .util .ArrayList ;
4+ import java .util .Arrays ;
5+ import java .util .LinkedList ;
46import java .util .List ;
7+ import java .util .Queue ;
58
69public class _417 {
710public static class Solution1 {
@@ -57,4 +60,64 @@ void dfs(int[][] matrix, boolean[][] visited, int height, int x, int y) {
5760 }
5861 }
5962
63+ public static class Solution2 {
64+ public List <List <Integer >>pacificAtlantic (int [][]matrix ) {
65+ List <List <Integer >>result =new ArrayList <>();
66+ if (matrix ==null ||matrix .length ==0 ||matrix [0 ].length ==0 ) {
67+ return result ;
68+ }
69+ int m =matrix .length ;
70+ int n =matrix [0 ].length ;
71+ for (int i =0 ;i <m ;i ++) {
72+ for (int j =0 ;j <n ;j ++) {
73+ boolean []touchesPacificAndAtlantic =new boolean [2 ];
74+ update (i ,j ,m ,n ,touchesPacificAndAtlantic );
75+ Queue <int []>queue =new LinkedList <>();
76+ boolean [][]visited =new boolean [m ][n ];
77+ visited [i ][j ] =true ;
78+ queue .offer (new int []{i ,j });
79+ if (bfs (matrix ,m ,n ,touchesPacificAndAtlantic ,queue ,visited )) {
80+ result .add (new ArrayList <>(Arrays .asList (i ,j )));
81+ }
82+ }
83+ }
84+ return result ;
85+ }
86+
87+ private void update (int i ,int j ,int m ,int n ,boolean []touchesPacificAndAtlantic ) {
88+ if (i ==0 ||j ==0 ) {
89+ touchesPacificAndAtlantic [0 ] =true ;
90+ }
91+ if (i ==m -1 ||j ==n -1 ) {
92+ touchesPacificAndAtlantic [1 ] =true ;
93+ }
94+ }
95+
96+ private boolean bfs (int [][]matrix ,int m ,int n ,boolean []touchesPacificAndAtlantic ,Queue <int []>queue ,boolean [][]visited ) {
97+ if (touchesPacificAndAtlantic [0 ] &&touchesPacificAndAtlantic [1 ]) {
98+ return true ;
99+ }
100+ int []directions =new int []{0 ,1 ,0 , -1 ,0 };
101+ while (!queue .isEmpty ()) {
102+ int size =queue .size ();
103+ for (int k =0 ;k <size ;k ++) {
104+ int []curr =queue .poll ();
105+ for (int p =0 ;p <directions .length -1 ;p ++) {
106+ int newx =curr [0 ] +directions [p ];
107+ int newy =curr [1 ] +directions [p +1 ];
108+ if (newx >=0 &&newx <m &&newy >=0 &&newy <n &&matrix [newx ][newy ] <=matrix [curr [0 ]][curr [1 ]] && !visited [newx ][newy ]) {
109+ visited [newx ][newy ] =true ;
110+ queue .offer (new int []{newx ,newy });
111+ update (newx ,newy ,m ,n ,touchesPacificAndAtlantic );
112+ if (touchesPacificAndAtlantic [0 ] &&touchesPacificAndAtlantic [1 ]) {
113+ return true ;
114+ }
115+ }
116+ }
117+ }
118+ }
119+ return false ;
120+ }
121+ }
122+
60123}