給定一個 m x n 的非負整數矩陣來表示一片大陸上各個單元格的高度。“太平洋”處于大陸的左邊界和上邊界，而“大西洋”處于大陸的右邊界和下邊界。規定水流只能按照上、下、左、右四個方向流動，且只能從高到低或者在同等高度上流動。請找出那些水流既可以流動到“太平洋”，又能流動到“大西洋”的陸地單元的坐標。提示：輸出坐標的順序不重要
m 和 n 都小于150示例：給定下面的 5x5 矩陣:太平洋 ~   ~   ~   ~   ~ ~  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  **   *   *   *   * 大西洋返回:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上圖中帶括號的單元).

代碼

class Solution {public boolean bound(int x,int y,int n,int m){return x>=0&&x<n&&y>=0&&y<m;}public List<List<Integer>> pacificAtlantic(int[][] matrix) {List<List<Integer>> res=new ArrayList<>();if(matrix.length==0) return res;int n=matrix.length,m=matrix[0].length;boolean[][] check=new boolean[n][m];boolean[][] seen=new boolean[n][m];Queue<int[]> queue=new LinkedList<>();int[][] dir=new int[][]{{-1,0},{1,0},{0,1},{0,-1}};for(int i=0;i<m;i++)//將從大西洋出發的入隊{queue.add(new int[]{0,i});check[0][i]=true;}for(int i=0;i<n;i++){queue.add(new int[]{i,0});check[i][0]=true;}while (!queue.isEmpty())//bfs搜索從大西洋出發可以到達的地方{int[] temp=queue.poll();int x=temp[0],y=temp[1];for (int[] d:dir){int nextX=x+d[0],nextY=y+d[1];if(bound(nextX,nextY,n,m)&&!check[nextX][nextY]&&matrix[nextX][nextY]>=matrix[x][y])//可以到達的地方{queue.add(new int[]{nextX,nextY});check[nextX][nextY]=true;}}}for(int i=0;i<m;i++)//將從太平洋出發的入隊{queue.add(new int[]{n-1,i});seen[n-1][i]=true;}for(int i=0;i<n;i++){if(!seen[i][m-1]){queue.add(new int[]{i,m-1});seen[i][m-1]=true;}}while (!queue.isEmpty())//bfs搜索太平洋出發能到達的點{int[] temp=queue.poll();int x=temp[0],y=temp[1];if(check[x][y]) res.add(new ArrayList(){{add(x);add(y);}});//如果當前節點也能從大西洋出發到達，則是結果for (int[] d:dir){int nextX=x+d[0],nextY=y+d[1];if(bound(nextX,nextY,n,m)&&!seen[nextX][nextY]&&matrix[nextX][nextY]>=matrix[x][y])//可以到達的地方{queue.add(new int[]{nextX,nextY});seen[nextX][nextY]=true;}}}return res;}
}