leetcode 417. Pacific Atlantic Water Flow | 417. 太平洋大西洋水流问题（DFS，经典“感染”思路）

阳光穿透心脏的1/2处 2022-09-03 01:22 84阅读 0赞

## 题目 ##

[https://leetcode.com/problems/pacific-atlantic-water-flow/][https_leetcode.com_problems_pacific-atlantic-water-flow]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

一开始的错误思路：（区分“主动”与“被动”的过程）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

正确答案参考视频：[https://leetcode-cn.com/problems/pacific-atlantic-water-flow/solution/java-si-lu-qing-xi-dai-ma-jian-ji-by-ven-4cds/][https_leetcode-cn.com_problems_pacific-atlantic-water-flow_solution_java-si-lu-qing-xi-dai-ma-jian-ji-by-ven-4cds]

看了视频的思路之后，发现其实这是一个经典的“感染”问题…代码迅速搞定。

class Solution { 
        int M;
        int N;
    
        public List<List<Integer>> pacificAtlantic(int[][] heights) { 
            M = heights.length;
            N = heights[0].length;
    
            boolean[][] seen = new boolean[M][N];
            boolean[][] LU = new boolean[M][N];
            for (int i = 0; i < M; i++) { 
                dfs(heights, LU, seen, i, 0);
            }
            for (int j = 0; j < N; j++) { 
                dfs(heights, LU, seen, 0, j);
            }
    
            boolean[][] RD = new boolean[M][N];
            seen = new boolean[M][N];
            for (int i = M - 1; i >= 0; i--) { 
                dfs(heights, RD, seen, i, N - 1);
            }
            for (int j = N - 1; j >= 0; j--) { 
                dfs(heights, RD, seen, M - 1, j);
            }
    
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < M; i++) { 
                for (int j = 0; j < N; j++) { 
                    if (LU[i][j] && RD[i][j]) { 
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(i);
                        list.add(j);
                        res.add(list);
                    }
                }
            }
            return res;
        }
    
        public void dfs(int[][] m, boolean[][] A, boolean[][] seen, int i, int j) { 
            if (i < 0 || j < 0 || i == M || j == N) return;
            seen[i][j] = true;
            A[i][j] = true;
            if (i > 0 && m[i - 1][j] >= m[i][j] && !seen[i - 1][j]) dfs(m, A, seen, i - 1, j);
            if (j > 0 && m[i][j - 1] >= m[i][j] && !seen[i][j - 1]) dfs(m, A, seen, i, j - 1);
            if (i < M - 1 && m[i + 1][j] >= m[i][j] && !seen[i + 1][j]) dfs(m, A, seen, i + 1, j);
            if (j < N - 1 && m[i][j + 1] >= m[i][j] && !seen[i][j + 1]) dfs(m, A, seen, i, j + 1);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_pacific-atlantic-water-flow]: https://leetcode.com/problems/pacific-atlantic-water-flow/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/4e73f0a22eda4d60b21c618efa578e0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/0d911ac0911a420a94aa4aa3578725e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20220829/69466c70142345a88dc0c89c9c15a071.png
[https_leetcode-cn.com_problems_pacific-atlantic-water-flow_solution_java-si-lu-qing-xi-dai-ma-jian-ji-by-ven-4cds]: https://leetcode-cn.com/problems/pacific-atlantic-water-flow/solution/java-si-lu-qing-xi-dai-ma-jian-ji-by-ven-4cds/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/bcdde169568240c2b3b340633f471edc.png