417. Pacific Atlantic Water Flow.md

417. Pacific Atlantic Water Flow

https://leetcode.com/problems/pacific-atlantic-water-flow/

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

1. The order of returned grid coordinates does not matter.
2. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

代码

• DFS

思路：先固定0和m-1列，往中间扩展，再固定0和n-1行，往中间扩展。我们取这两种都能访问到的位置，也就是答案。

class Solution {
    private int[] dirs = {-1, 0, 1, 0, -1};
    private int n, m;
    private int MIN = Integer.MIN_VALUE;
    private List<List<Integer>> res = new ArrayList<>();
    private boolean[][] atl, pac;
    private int[][] matrix;
    public void dfs(int x, int y, int prev, boolean[][] v) {
        if (x < 0 || y < 0 || x >= n || y >= m || v[x][y] || matrix[x][y] < prev)
            return;
        v[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int px, py;
            px = x + dirs[i];
            py = y + dirs[i + 1];
            dfs(px, py, matrix[x][y], v);
        }
    }
    
    public List<List<Integer>> pacificAtlantic(int[][] _matrix) {
        if (_matrix == null || _matrix.length == 0 || _matrix[0].length == 0) return res;
        matrix = _matrix;
        n = matrix.length; m = matrix[0].length;
        atl = new boolean[n][m]; pac = new boolean[n][m];
        // first col, last col
        for (int i = 0; i < n; i++) {
            dfs(i, 0, MIN, pac);
            dfs(i, m - 1, MIN, atl);
        }
        for (int j = 0; j < m; j++) {
            dfs(0, j, MIN, pac);
            dfs(n - 1, j, MIN, atl);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (pac[i][j] && atl[i][j]) res.add(Arrays.asList(i, j));
            }
        }
        return res;
    }
}

class Solution:
    def pacificAtlantic(self, matrix):
        # Check for an empty graph.
        if not matrix:
            return []

        p_visited = set()
        a_visited = set()
        rows, cols = len(matrix), len(matrix[0])
        directions = ((0, 1), (0, -1), (1, 0), (-1, 0))

        def traverse(i, j, visited):
            if (i, j) in visited:
                return
            visited.add((i, j))
            # Traverse neighbors.
            for direction in directions:
                next_i, next_j = i + direction[0], j + direction[1]
                if 0 <= next_i < rows and 0 <= next_j < cols:
                    # Add in your question-specific checks.
                    if matrix[next_i][next_j] >= matrix[i][j]:
                        traverse(next_i, next_j, visited)

        for row in range(rows):
            traverse(row, 0, p_visited)
            traverse(row, cols - 1, a_visited)

        for col in range(cols):
            traverse(0, col, p_visited)
            traverse(rows - 1, col, a_visited)

        return list(p_visited & a_visited)

• BFS

class Solution(object):
    def pacificAtlantic(self, grid):
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """

        return solve(grid)


dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n, m = 0, 0

def solve(grid):
    if not grid or len(grid[0]) == 0:
        return []
    global n, m, st
    n, m = len(grid), len(grid[0])
    st = [[0] * m for _ in range(n)] # use 2 bits, 01 for Pacific, 10 for Atlantic, 11 for both
    
    for i in range(n):
        dfs(i, 0, 1, grid)
    for i in range(n):
        dfs(i, m-1, 2, grid)
    for j in range(m):
        dfs(0, j, 1, grid)
    for j in range(m):
        dfs(n-1, j, 2, grid)
        
    res = []
    for i in range(n):
        for j in range(m):
            if st[i][j] == 3:
                # both can flow
                res.append([i, j])
    return res


def dfs(x, y, k, grid):
    global st
    if st[x][y] & k:    return
    st[x][y] |= k
    for i in range(4):
        new_x, new_y = x + dx[i], y + dy[i]
        global n, m
        if (new_x >= 0 and new_x < n and new_y >= 0 and new_y < m and grid[x][y] <= grid[new_x][new_y]):
            dfs(new_x, new_y, k, grid)