java DFS from the ocean to ground just 20 ms


  • 0
    T
    public List<int[]> pacificAtlantic(int[][] matrix) {
            if (matrix.length == 0) {
                return new ArrayList<>();
            }
            List<int[]> res = new ArrayList<>();
            int r = matrix.length;
            int c = matrix[0].length;
            boolean[][] pac = new boolean[r][c];
            boolean[][] alt = new boolean[r][c];
            /*scan the row*/
            for (int i = 0 ; i < c ;i ++) {
                pac[0][i] = true;
                alt[r - 1][i] = true;
                DFS(matrix, pac, 0, i);
                DFS(matrix, alt, r - 1, i);
            }
            /*scan the column*/
            for (int i = 0; i < r; i ++) {
                pac[i][0] = true;
                alt[i][c - 1] = true;
                DFS(matrix, pac, i, 0);
                DFS(matrix, alt, i, c - 1);
            }
            /*get the point*/
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    if (pac[i][j] && alt[i][j]) {
                        int[] a = new int[2];
                        a[0] = i;
                        a[1] = j;
                        res.add(a);
                    }
                }
            }
            return res;
        }
        //dfs
        private void DFS(int[][] matrix, boolean[][] pac, int i, int j) {
            //up
            if (i > 0 && matrix[i - 1][j] >= matrix[i][j] && !pac[i - 1][j]) {
                pac[i - 1][j] = true;
                DFS(matrix, pac, i - 1, j);
            }
    
            //down
            if (i < matrix.length - 1 &&  matrix[i + 1][j] >= matrix[i][j] && !pac[i + 1][j]) {
                pac[i + 1][j] = true;
                DFS(matrix, pac, i + 1, j);
            }
    
            //left
            if (j > 0 && matrix[i][j - 1] >= matrix[i][j] &&  !pac[i][j - 1]) {
                pac[i][j - 1] = true;
                DFS(matrix, pac, i, j - 1);
            }
            // right
            if (j < matrix[0].length - 1 && matrix[i][j + 1] >= matrix[i][j] && !pac[i][j + 1]) {
                pac[i][j + 1] = true;
                DFS(matrix, pac, i, j + 1);
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.