有一个 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;}
}
}
要识别水可以流向太平洋和大西洋的单元,您需要分别跟踪可以到达每个海洋的单元。然后,找到这些单元格集合的交集。可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历矩阵。
您当前的实施存在几个问题:
dfs
功能不区分太平洋和大西洋搜索。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);
}
}
pacific
和atlantic
,以分别跟踪可以流向太平洋和大西洋的细胞。pacific
和 atlantic
矩阵中标记为 true 的单元来检查哪些单元可以流向两个海洋。此修订后的解决方案可确保我们正确跟踪可以到达太平洋和大西洋的细胞,并应通过所有测试用例。