LeetCode 417. Pacific Atlantic Water Flow _太平洋大西洋水流问题

题目描述

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：

1. 输出坐标的顺序不重要
2. 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]] (上图中带括号的单元).

分别从太平洋沿岸和大西洋沿岸进行深搜，满足条件的在各自的标志二维数组flag中做标志，最后遍历两个二维数组，如果同个位置都没标记过，说明这个位置可到达太平洋和大西洋。

        public List pacificAtlantic(int[][] matrix) {List list = new ArrayList();if (matrix.length <= 0 || matrix[0].length <= 0)return list;int rows = matrix.length;int cols = matrix[0].length;byte[][] flag1 = new byte[rows][cols];byte[][] flag2 = new byte[rows][cols];for (int i = 0; i < cols; i++) {dfs(matrix, flag1, 0, i);dfs(matrix, flag2, rows - 1, i);}for (int i = 0; i < rows; i++) {dfs(matrix, flag1, i, 0);dfs(matrix, flag2, i, cols - 1);}for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (flag1[i][j] == 1 && flag2[i][j] == 1)list.add(new int[] { i, j });}}return list;}private void dfs(int[][] matrix, byte[][] flag, int x, int y) {int rows = matrix.length;int cols = matrix[0].length;flag[x][y] = 1;// 上if (x - 1 >= 0 && matrix[x - 1][y] >= matrix[x][y] && flag[x - 1][y] != 1)dfs(matrix, flag, x - 1, y);// 下if (x + 1 < rows && matrix[x + 1][y] >= matrix[x][y] && flag[x + 1][y] != 1)dfs(matrix, flag, x + 1, y);// 左if (y - 1 >= 0 && matrix[x][y - 1] >= matrix[x][y] && flag[x][y - 1] != 1)dfs(matrix, flag, x, y - 1);// 右if (y + 1 < cols && matrix[x][y + 1] >= matrix[x][y] && flag[x][y + 1] != 1)dfs(matrix, flag, x, y + 1);}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！