Java BFS & DFS from Ocean
Two Queue and add all the Pacific border to one queue; Atlantic border to another queue.\n2. Keep a visited matrix for each queue. In the end, add the cell visi
1. Two Queue and add all the Pacific border to one queue; Atlantic border to another queue.\n2. Keep a visited matrix for each queue. In the end, add the cell visited by two queue to the result.\nBFS: Water flood from ocean to the cell. Since water can only flow from high/equal cell to low cell, add the neighboor cell with height larger or equal to current cell to the queue and mark as visited.\n```\npublic class Solution {\n    int[][]dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};\n    public List<int[]> pacificAtlantic(int[][] matrix) {\n        List<int[]> res = new LinkedList<>();\n        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){\n            return res;\n        }\n        int n = matrix.length, m = matrix[0].length;\n        //One visited map for each ocean\n        boolean[][] pacific = new boolean[n][m];\n        boolean[][] atlantic = new boolean[n][m];\n        Queue<int[]> pQueue = new LinkedList<>();\n        Queue<int[]> aQueue = new LinkedList<>();\n        for(int i=0; i<n; i++){ //Vertical border\n            pQueue.offer(new int[]{i, 0});\n            aQueue.offer(new int[]{i, m-1});\n            pacific[i][0] = true;\n            atlantic[i][m-1] = true;\n        }\n        for(int i=0; i<m; i++){ //Horizontal border\n            pQueue.offer(new int[]{0, i});\n            aQueue.offer(new int[]{n-1, i});\n            pacific[0][i] = true;\n            atlantic[n-1][i] = true;\n        }\n        bfs(matrix, pQueue, pacific);\n        bfs(matrix, aQueue, atlantic);\n        for(int i=0; i<n; i++){\n            for(int j=0; j<m; j++){\n                if(pacific[i][j] && atlantic[i][j])\n                    res.add(new int[]{i,j});\n            }\n        }\n        return res;\n    }\n    public void bfs(int[][]matrix, Queue<int[]> queue, boolean[][]visited){\n        int n = matrix.length, m = matrix[0].length;\n        while(!queue.isEmpty()){\n            int[] cur = queue.poll();\n            for(int[] d:dir){\n                int x = cur[0]+d[0];\n                int y = cur[1]+d[1];\n                if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < matrix[cur[0]][cur[1]]){\n                    continue;\n                }\n                visited[x][y] = true;\n                queue.offer(new int[]{x, y});\n            } \n        }\n    }\n}\n````\nDFS version:\n```\npublic class Solution {\n    public List<int[]> pacificAtlantic(int[][] matrix) {\n        List<int[]> res = new LinkedList<>();\n        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){\n            return res;\n        }\n        int n = matrix.length, m = matrix[0].length;\n        boolean[][]pacific = new boolean[n][m];\n        boolean[][]atlantic = new boolean[n][m];\n        for(int i=0; i<n; i++){\n            dfs(matrix, pacific, Integer.MIN_VALUE, i, 0);\n            dfs(matrix, atlantic, Integer.MIN_VALUE, i, m-1);\n        }\n        for(int i=0; i<m; i++){\n            dfs(matrix, pacific, Integer.MIN_VALUE, 0, i);\n            dfs(matrix, atlantic, Integer.MIN_VALUE, n-1, i);\n        }\n        for (int i = 0; i < n; i++) \n            for (int j = 0; j < m; j++) \n                if (pacific[i][j] && atlantic[i][j]) \n                    res.add(new int[] {i, j});\n        return res;\n    }\n    \n    int[][]dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};\n    \n    public void dfs(int[][]matrix, boolean[][]visited, int height, int x, int y){\n        int n = matrix.length, m = matrix[0].length;\n        if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < height)\n            return;\n        visited[x][y] = true;\n        for(int[]d:dir){\n            dfs(matrix, visited, matrix[x][y], x+d[0], y+d[1]);\n        }\n    }\n}\n````
[]