417. Pacific Atlantic Water Flow

417. Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note: The order of returned grid coordinates does not matter. Both m and n are less than 150. Example:

Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~ ~ 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 * * * * * * AtlanticReturn:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in

思路： 题目给了一个矩阵，代表一个高度，高度高的可以流到同高度或更小的高度那里 而在矩阵的四周，围绕着太平洋和大西洋（可以看图示，太平洋左边和上边，大西洋下边和右边，也就是这四个边对应的位置是通向海洋的） 现在问说这个矩阵里面的位置，那些的水流可以同时流到大西洋和太平洋？ 如果准备一个位置一个位置的去寻找能否有路径能够到达两个海洋，就太naïve了。 1、分别处理每个海洋，从海洋边缘（每个海洋两条边）开始，一步步的搜索，即从连接海洋的地方还是搜索，哪些节点的高度高于等于自身（反过来就是可以从那里流到自己），如果是，就标记为true，就这样不断搜索下去。最后所有标记为true的位置就是可以流到对应的海洋。 2、找这两个矩阵，同为true的输出，就是都能流到两个海洋的位置

class Solution { int dx[] = {0,0,-1,1}; int dy[] = {1,-1,0,0}; //判断一个节点能否流通到海洋 private void flow(boolean visited[][], int matrix[][], int x, int y, int n, int m ){ visited[x][y] = true; for(int i = 0;i < 4;i++){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 0 && nx < n && ny >= 0 && ny < m){ //一个节点是只能留到不高于自己高度的节点，但是我们这里是反过来找能从nxny留到xy的节点，所以这里注意下 if(visited[nx][ny] == false && matrix[nx][ny] >= matrix[x][y]) flow(visited, matrix, nx, ny, n, m); } } } public List pacificAtlantic(int[][] matrix) { List res = new ArrayList(); int n = matrix.length; if(n == 0) return res; int m = matrix[0].length; boolean PV[][] = new boolean[n][m]; boolean AV[][] = new boolean[n][m]; // 这里从所有临海的地方到这回去判断某个节点是否能流到对应的地方 for(int i = 0;i < n;i++){ flow(PV, matrix, i, 0, n, m); flow(AV, matrix, i, m - 1, n, m); } for(int i = 0;i < m;i++){ flow(PV, matrix, 0, i, n, m); flow(AV, matrix, n - 1, i, n, m); } for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(PV[i][j] && AV[i][j]) res.add(new int[] {i, j}); } } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。