Leetcode 417：太平洋大西洋水流

Question

有一个 m x n 的矩形岛屿，与太平洋和大西洋接壤。太平洋接触岛屿的左侧和顶部边缘，大西洋接触岛屿的右侧和底部边缘。

岛屿被划分为方形网格。给定一个 m x n 整数矩阵高度，其中 heights[r][c] 表示坐标 (r, c) 处单元格的海拔高度。

岛屿降雨较多，如果相邻单元格的高度小于或等于当前单元格的高度，雨水可以直接流向北、南、东、西的相邻单元格。水可以从与海洋相邻的任何细胞流入海洋。

返回网格坐标结果的二维列表，其中 result[i] = [ri, ci] 表示雨水可以从单元格 (ri, ci) 流向太平洋和大西洋。 https://leetcode.com/problems/pacific-atlantic-water-flow/submissions/1325130729/

这是我的代码，它几乎没有通过任何测试用例。有人能帮忙指出其中的逻辑缺陷吗？我觉得这似乎是正确的。

class Solution {
   public List<List<Integer>> pacificAtlantic(int[][] heights) {
       List<List<Integer>> list = new ArrayList<>();
       int size = heights[0].length;
       for(int i = 0; i<heights.length; i++) {
       for(int j =0; j< size; j++) {
         Set<String> visited = new HashSet<>();
               if(dfs(heights, i, j, heights[i][j], visited)==true) {
                   List<Integer> add1 = new ArrayList<>();
           add1.add(i);
           add1.add(j);
           list.add(add1);
               }
               
           
       }
       
    }
    return list;



   }
   
   public boolean dfs(int[][] grid, int row, int col, int prev, Set<String> visited) {
       
       if(row==grid.length || row<0 || col<0 || col==grid[0].length) {
           return true;
       }
       if(grid[row][col]> prev || visited.contains(row + "," + col)) {
           return false;
       }
       else{
           prev = grid[row][col];
            
       }
       visited.add(row + "," + col);
       boolean down = dfs(grid, row+1, col, prev, visited);
       boolean up =  dfs(grid, row-1, col, prev, visited);
       boolean left = dfs(grid, row, col-1, prev, visited);
       boolean right =   dfs(grid, row, col+1, prev, visited);
         
         visited.remove(row + "," + col);
          if(row==grid.length-1 || row==0 || col==0 || col==grid[0].length-1) {
           
          if( (up && right) || (up && down) || (right && left) ||(left && down)) {
         
           return true;
          }
          else{return false;}
          }

          else{return up|| down|| right|| left;}
   }
}

Answer 1

要识别水可以流向太平洋和大西洋的单元，您需要分别跟踪可以到达每个海洋的单元。然后，找到这些单元格集合的交集。可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历矩阵。

您当前的实施存在几个问题：

1. dfs

   功能不区分太平洋和大西洋搜索。
2. 它无法正确处理可以到达两个海洋的细胞的边界条件。
3. 您正在重新初始化每个单元格的

   visited

   集，这会导致错误的结果。

这是您的解决方案的修订版本，使用来自太平洋和大西洋边缘的两个单独的 DFS 搜索：

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new ArrayList<>();
        if (heights == null || heights.length == 0 || heights[0].length == 0) return result;
        
        int m = heights.length;
        int n = heights[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            dfs(heights, pacific, Integer.MIN_VALUE, i, 0);
            dfs(heights, atlantic, Integer.MIN_VALUE, i, n - 1);
        }
        
        for (int j = 0; j < n; j++) {
            dfs(heights, pacific, Integer.MIN_VALUE, 0, j);
            dfs(heights, atlantic, Integer.MIN_VALUE, m - 1, j);
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        
        return result;
    }
    
    private void dfs(int[][] heights, boolean[][] visited, int height, int x, int y) {
        int m = heights.length;
        int n = heights[0].length;
        if (x < 0 || y < 0 || x >= m || y >= n || visited[x][y] || heights[x][y] < height) {
            return;
        }
        visited[x][y] = true;
        dfs(heights, visited, heights[x][y], x + 1, y);
        dfs(heights, visited, heights[x][y], x - 1, y);
        dfs(heights, visited, heights[x][y], x, y + 1);
        dfs(heights, visited, heights[x][y], x, y - 1);
    }
}

说明

1. 初始化：我们初始化两个布尔矩阵，

   pacific

   和

   atlantic

   ，以分别跟踪可以流向太平洋和大西洋的细胞。
2. DFS from Edges：从太平洋和大西洋边缘执行 DFS：
   • 对于太平洋：从顶行和左列开始 DFS。
   • 对于大西洋：从底行和右列开始 DFS。
3. DFS 逻辑：如果单元格之前未被访问过并且其高度大于或等于前一个单元格的高度，则 DFS 函数会将单元格标记为已访问。
4. 结果编译：在 DFS 遍历之后，我们通过查找

   pacific

   和

   atlantic

   矩阵中标记为 true 的单元来检查哪些单元可以流向两个海洋。

此修订后的解决方案可确保我们正确跟踪可以到达太平洋和大西洋的细胞，并应通过所有测试用例。