关于leetcode417号问题

Question

老师您好，关于这个问题我的思路是这样的：先遍历整个网格找出所有既能去往大西洋又能去往太平洋的点，并使用数组canGo存储这些点，其中可以满足条件的点canGo值为1，还未遍历的是-1，遍历过去不了的是0；最后再一次性将所有点存储到结果列表res中；虽然通过了测试，但是时间并不理想，请问这种方法有什么比较好的优化方式吗？
另外，在dfs函数中，我本来另外还加了一个判断条件，就是canGo[x][y] == 0的时候直接返回false，我本来是这么想的：访问到该点不能同时去到太平洋和大西洋，所以这条路径不满足条件，想通过这种方法进行一部分剪枝，但是实际提交这样却过不了，请问这是为什么？

public class PacificAtlanticWaterFlow {
    private int[][] matrix;
    private int[][] canGo;
    private int R, C;
    private static int[][] d  = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private boolean pacific = false, atlantic = false;
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return res;
        this.matrix = matrix;
        R = matrix.length;
        C = matrix[0].length;
        canGo = new int[R][C];//-1: 未定， 0：去不了， 1：可以去
        for(int i = 0; i < R; i ++)
            Arrays.fill(canGo[i], -1);

        for(int i = 0; i < R; i ++)
            for(int j = 0; j < C; j ++)
                if(canGo[i][j] == -1){
                    boolean[][] onPath = new boolean[R][C];
                    pacific = false;
                    atlantic = false;
                    if(dfs(i, j, onPath))
                        canGo[i][j] = 1;
                    else
                        canGo[i][j] = 0;
                }

        for(int i = 0; i < R; i ++)
            for(int j = 0; j < C; j ++)
                if(canGo[i][j] == 1){
                    ArrayList list = new ArrayList();
                    list.add(i);
                    list.add(j);
                    res.add(list);
                }
        return res;
    }
    private boolean dfs(int x, int y, boolean[][] onPath){
        if(canGo[x][y] == 1) return true;
        if(x == 0 || y == 0) pacific = true;
        if(x == R - 1 || y == C - 1) atlantic = true;
        if(pacific && atlantic) return true;

        onPath[x][y] = true;
        for(int i = 0; i < 4; i ++){
            int newX = x + d[i][0];
            int newY = y + d[i][1];
            if(inArea(newX, newY) && !onPath[newX][newY] && matrix[newX][newY] <= matrix[x][y])
                if(dfs(newX, newY, onPath)) return true;
        }
        return false;
    }
    private boolean inArea(int x, int y){
        return x >= 0 && x < R && y >= 0 && y < C;
    }
}

Answer 1

liuyubobobo 2019-11-01 14:26:13

可以尝试反向从边界点进行 dfs，看从大西洋能到哪些顶点，从太平洋能到哪些顶点。最后，从大西洋能到达，同时从太平洋也能到达的点，就是答案。这丫昂做，不需要每个点都 dfs，只对边上的点 dfs：）

我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0417-Pacific-Atlantic-Water-Flow/java-0417/src/Solution.java

至于你说的问题，在 Leetcode 上，如果提交错误，会告诉你具体错误的测试用例。用这个测试用例实际单步调试跟踪一下，看看自己的代码为什么返回了错误的结果？而不要仅仅对着代码。很多时候，一调试，就能找到自己的思维漏洞了，进步就发生在这个过程中哦。

加油！：）