Share one easy-understanding DFS solution


  • 0
    H
    public class Solution {
        
        int[][] matrix;
        int m, n;
        int[] idx_arr = {1,0,-1,0,1};
        
        public List<int[]> pacificAtlantic(int[][] matrix) {
            List<int[]> res = new ArrayList<>();
            if (matrix.length == 0 || matrix[0].length == 0) return res;
            this.matrix = matrix;
            m = matrix.length;
            n = matrix[0].length;
            
            Set<String> pacific = new HashSet<>();
            Set<String> atlantic = new HashSet<>();
            
            for (int row = 0; row < m; row ++) dfs(row, 0, pacific);
            for (int col = 0; col < n; col ++) dfs(0, col, pacific);
            for (int row = 0; row < m; row ++) dfs(row, n-1, atlantic);
            for (int col = 0; col < n; col ++) dfs(m-1, col, atlantic);
            
            for (String p : atlantic) {
                if (pacific.contains(p)) {
                    String[] ps = p.split(",");
                    res.add(new int[]{Integer.valueOf(ps[0]), Integer.valueOf(ps[1])});
                }
            }
            
            return res;
        }
        
        private void dfs(int row, int col, Set<String> set) {
            if (set.contains(row + "," + col)) return;
            set.add(row + "," + col);
            
            for (int idx = 0; idx < 4; idx ++) {
                int newRow = row + idx_arr[idx];
                int newCol = col + idx_arr[idx+1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n 
                && matrix[newRow][newCol] >= matrix[row][col]) {
                    dfs(newRow, newCol, set);
                }
            }
        }
    }
    

Log in to reply
 

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