給定一個 m x n 的非負整數(shù)矩陣來表示一片大陸上各個單元格的高度。“太平洋”處于大陸的左邊界和上邊界，而“大西洋”處于大陸的右邊界和下邊界。規(guī)定水流只能按照上、下、左、右四個方向流動，且只能從高到低或者在同等高度上流動。請找出那些水流既可以流動到“太平洋”，又能流動到“大西洋”的陸地單元的坐標。提示：輸出坐標的順序不重要 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++)//將從大西洋出發(fā)的入隊{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搜索從大西洋出發(fā)可以到達的地方{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++)//將從太平洋出發(fā)的入隊{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搜索太平洋出發(fā)能到達的點{int[] temp=queue.poll();int x=temp[0],y=temp[1];if(check[x][y]) res.add(new ArrayList(){{add(x);add(y);}});//如果當前節(jié)點也能從大西洋出發(fā)到達，則是結果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;} }

總結

以上是生活随笔為你收集整理的leetcode417. 太平洋大西洋水流问题(bfs)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。