|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.List; |
| 5 | +/**Given the following 5x5 matrix: |
| 6 | +
|
| 7 | + Pacific ~ ~ ~ ~ ~ |
| 8 | + ~ 1 2 2 3 (5) * |
| 9 | + ~ 3 2 3 (4) (4) * |
| 10 | + ~ 2 4 (5) 3 1 * |
| 11 | + ~ (6) (7) 1 4 5 * |
| 12 | + ~ (5) 1 1 2 4 * |
| 13 | + * * * * * Atlantic |
| 14 | +
|
| 15 | +Return: |
| 16 | +
|
| 17 | +[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).*/ |
| 18 | + |
| 19 | +publicclassPacificAtlanticWaterFlow { |
| 20 | +//looked at this post: https://discuss.leetcode.com/topic/62379/java-bfs-dfs-from-ocean |
| 21 | + |
| 22 | +/**One typical trick to work on 2d grid problems is to go through the border and put proper ones into a queue if using BFS.*/ |
| 23 | +publicList<int[]>pacificAtlantic(int[][]matrix) { |
| 24 | + |
| 25 | +List<int[]>result =newArrayList(); |
| 26 | +if(matrix ==null ||matrix.length ==0 ||matrix[0].length ==0)returnresult; |
| 27 | + |
| 28 | +intm =matrix.length,n =matrix[0].length; |
| 29 | +boolean[][]pacific =newboolean[m][n]; |
| 30 | +boolean[][]atlantic =newboolean[m][n]; |
| 31 | + |
| 32 | +for(inti =0;i <m;i++){ |
| 33 | +dfs(matrix,pacific,Integer.MIN_VALUE,i,0); |
| 34 | +dfs(matrix,atlantic,Integer.MIN_VALUE,i,n-1); |
| 35 | + } |
| 36 | + |
| 37 | +for(inti =0;i <n;i++){ |
| 38 | +dfs(matrix,pacific,Integer.MIN_VALUE,0,i); |
| 39 | +dfs(matrix,atlantic,Integer.MIN_VALUE,m-1,i); |
| 40 | + } |
| 41 | + |
| 42 | +for(inti =0;i <m;i++){ |
| 43 | +for(intj =0;j <n;j++){ |
| 44 | +if(pacific[i][j] &&atlantic[i][j]){ |
| 45 | +result.add(newint[]{i,j}); |
| 46 | + } |
| 47 | + } |
| 48 | + } |
| 49 | + |
| 50 | +returnresult; |
| 51 | + } |
| 52 | + |
| 53 | +voiddfs(int[][]matrix,boolean[][]visited,intheight,intx,inty){ |
| 54 | +intm =matrix.length,n =matrix[0].length; |
| 55 | +if(x <0 ||y <0 ||x >=m ||y >=n ||matrix[x][y] <height ||visited[x][y])return; |
| 56 | +visited[x][y] =true; |
| 57 | +dfs(matrix,visited,matrix[x][y],x+1,y); |
| 58 | +dfs(matrix,visited,matrix[x][y],x,y+1); |
| 59 | +dfs(matrix,visited,matrix[x][y],x-1,y); |
| 60 | +dfs(matrix,visited,matrix[x][y],x,y-1); |
| 61 | + } |
| 62 | + |
| 63 | +publicstaticvoidmain(String...args){ |
| 64 | +PacificAtlanticWaterFlowtest =newPacificAtlanticWaterFlow(); |
| 65 | +// int[][] matrix = new int[][]{ |
| 66 | +// {1,2,2,3,5}, |
| 67 | +// {3,2,3,4,4}, |
| 68 | +// {2,4,5,3,1}, |
| 69 | +// {6,7,1,4,5}, |
| 70 | +// {5,1,1,2,4}, |
| 71 | +// }; |
| 72 | + |
| 73 | +// int[][] matrix = new int[][]{//this one is correct |
| 74 | +// {3,5}, |
| 75 | +// {4,4}, |
| 76 | +// }; |
| 77 | + |
| 78 | +// int[][] matrix = new int[][]{//this one is correct |
| 79 | +// {2,3,5}, |
| 80 | +// {3,4,4}, |
| 81 | +// }; |
| 82 | + |
| 83 | +int[][]matrix =newint[][]{ |
| 84 | + {2,3,5}, |
| 85 | + {3,4,4}, |
| 86 | + {5,3,1}, |
| 87 | + }; |
| 88 | +List<int[]>result =test.pacificAtlantic(matrix); |
| 89 | +for(int[]point :result){ |
| 90 | +System.out.println(point[0] +"\t" +point[1]); |
| 91 | + } |
| 92 | + } |
| 93 | + |
| 94 | +} |