417. Pacific Atlantic Water Flow - Medium

前往題目

想法

• 用DFS但不知道該怎麼處理重複visit的部分，不處理的話就會變成$O(M*N)^2$

思路

1. 從上下左右開始往內檢查，因為上下左右一定可以碰到其中一個海洋，或甚至兩個海洋都碰到
2. 每個cell都檢查其是否比前一個cell大，是的話就標記為true，不是的話直接return。因為這代表當前cell沒辦法流過前一個cell
3. 最後看哪些cell能碰到兩個海洋就是答案

這題我覺得蠻難的，腦袋需要轉彎

Code

JAVA解答

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();

        final int ROWS = heights.length, COLS = heights[0].length;
        boolean[][] pacific = new boolean[ROWS][COLS];
        boolean[][] atlantic = new boolean[ROWS][COLS];

        for (int c = 0; c < COLS; ++c) {
            // Go through the first row
            dfs(heights, 0, c, Integer.MIN_VALUE, pacific);
            // Last row
            dfs(heights, ROWS - 1, c, Integer.MIN_VALUE, atlantic);
        }

        for (int r = 0; r < ROWS; ++r) {
            // Go through first column
            dfs(heights, r, 0, Integer.MIN_VALUE, pacific);
            // Last column
            dfs(heights, r, COLS - 1, Integer.MIN_VALUE, atlantic);
        }

        // Save the cell that can reach pacific and atlantic
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                if (pacific[r][c] && atlantic[r][c]) {
                    res.add(List.of(r, c));
                }
            }
        }
        return res;
    }

    private void dfs(
        int[][] heights,
        int row, 
        int col,
        int prev,
        boolean[][] ocean 
        ) {
            // Check in bound
            if (row < 0 || row >= ocean.length || col < 0 || col >= ocean[0].length) return;
            // Check reachable -> pacific | 1 | 2 | 3
            // Previous must be smaller or equal to the current
            if (heights[row][col] < prev || ocean[row][col]) return;
            
            // Current cell can reach one of the ocean
            ocean[row][col] = true;
            
            // Check North, South, East, and West
            dfs(heights, row + 1, col, heights[row][col], ocean);
            dfs(heights, row - 1, col, heights[row][col], ocean);
            dfs(heights, row, col + 1, heights[row][col], ocean);
            dfs(heights, row, col - 1, heights[row][col], ocean);
        
    }
}

2024/04/22

• 沒寫出來，關鍵點是從四邊進攻分別紀錄能不能抵達pacific或atlantic