417. Pacific Atlantic Water Flow

题目链接：

思路是分别找到pacific和atlantic能够流到的地方，然后求两个地方的交集。找pacific和atlantic能流到的地方，就是这个matrix的遍历过程，可以用dfs或者bfs。复杂度没什么差，dfs写起来简单点。

public class Solution {    public List
    
      pacificAtlantic(int[][] matrix) {        List
     
       result = new ArrayList();        if(matrix.length == 0 || matrix[0].length == 0) return result;                m = matrix.length;        n = matrix[0].length;        boolean[][] pacific = new boolean[m][n];        boolean[][] atlantic = new boolean[m][n];        // dfs, for each position        for(int i = 0; i < m; i++) {            dfs(matrix, i, 0, pacific);            dfs(matrix, i, n- 1, atlantic);        }        for(int j = 0; j < n; j++) {            dfs(matrix, 0, j, pacific);            dfs(matrix, m - 1, j, atlantic);        }        // find the intersection        for(int i = 0; i < m; i++) {            for(int j = 0; j < n; j++) {                if(pacific[i][j] && atlantic[i][j]) result.add(new int[] {i, j});            }        }        return result;    }        int m, n;    int[][] dirs = {
   {0, -1}, {0, 1}, {-1, 0}, {1, 0}};    private void dfs(int[][] matrix, int x, int y, boolean[][] visited) {        if(visited[x][y]) return;        visited[x][y] = true;        for(int[] dir : dirs) {            int nx = x + dir[0], ny = y + dir[1];            if(nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[x][y] <= matrix[nx][ny]) {                dfs(matrix, nx, ny, visited);            }        }    }}