leetcode417. 太平洋大西洋水流问题(bfs)

给定一个 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;} }

总结

以上是生活随笔为你收集整理的leetcode417. 太平洋大西洋水流问题(bfs)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。