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<int[]> pacificAtlantic(int[][] matrix) {
		List<int[]> list = new ArrayList<int[]>();
 
		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);
 
	}