← Static tasks

417. Pacific Atlantic Water Flow

leetcode medium

#array#bit-manipulation#csharp#graph#leetcode#matrix#medium#search#stack

Task

Имеется прямоугольный остров размером m x n, который граничит с Тихим и Атлантическим океанами. Тихий океан касается левого и верхнего краев острова, а Атлантический океан - правого и нижнего краев. Остров разбит на сетку квадратных ячеек. Вам дана целочисленная матрица heights размером m x n, где heights[r][c] - высота над уровнем моря клетки с координатами (r, c). На острове выпадает много осадков, и дождевая вода может стекать в соседние клетки прямо на север, юг, восток и запад, если высота соседней клетки меньше или равна высоте текущей клетки. Вода может течь из любой клетки, прилегающей к океану, в океан. Верните двумерный список координат сетки result, где result[i] = [ri, ci] означает, что дождевая вода может течь из клетки (ri, ci) как в Тихий, так и в Атлантический океаны.

Пример:

Input: heights = [[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]]

Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

C# solution

matched/original
public class Solution {
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        int m = heights.Length;
        int n = heights[0].Length;
        bool[][] pacific = new bool[m][];
        bool[][] atlantic = new bool[m][];
        for (int i = 0; i < m; i++) {
            pacific[i] = new bool[n];
            atlantic[i] = new bool[n];
        }
        int[][] directions = new int[][] { new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1} };
        
        for (int i = 0; i < m; i++) {
            Dfs(i, 0, pacific, heights, directions);
            Dfs(i, n - 1, atlantic, heights, directions);
        }
        for (int j = 0; j < n; j++) {
            Dfs(0, j, pacific, heights, directions);
            Dfs(m - 1, j, atlantic, heights, directions);
        }
        
        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.Add(new List<int> { i, j });
                }
            }
        }
        return result;
    }
    
    private void Dfs(int r, int c, bool[][] ocean, int[][] heights, int[][] directions) {
        ocean[r][c] = true;
        foreach (int[] dir in directions) {
            int nr = r + dir[0];
            int nc = c + dir[1];
            if (nr >= 0 && nc >= 0 && nr < heights.Length && nc < heights[0].Length && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                Dfs(nr, nc, ocean, heights, directions);
            }
        }
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<vector<int>> PacificAtlantic(int[][] heights) {
        int m = heights.size();
        int n = heights[0].size();
        bool[][] pacific = new bool[m][];
        bool[][] atlantic = new bool[m][];
        for (int i = 0; i < m; i++) {
            pacific[i] = new bool[n];
            atlantic[i] = new bool[n];
        }
        int[][] directions = new int[][] { new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1} };
        
        for (int i = 0; i < m; i++) {
            Dfs(i, 0, pacific, heights, directions);
            Dfs(i, n - 1, atlantic, heights, directions);
        }
        for (int j = 0; j < n; j++) {
            Dfs(0, j, pacific, heights, directions);
            Dfs(m - 1, j, atlantic, heights, directions);
        }
        
        IList<vector<int>> result = new List<vector<int>>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.push_back(new List<int> { i, j });
                }
            }
        }
        return result;
    }
    
    private void Dfs(int r, int c, bool[][] ocean, int[][] heights, int[][] directions) {
        ocean[r][c] = true;
        foreach (vector<int>& dir in directions) {
            int nr = r + dir[0];
            int nc = c + dir[1];
            if (nr >= 0 && nc >= 0 && nr < heights.size() && nc < heights[0].size() && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                Dfs(nr, nc, ocean, heights, directions);
            }
        }
    }
}

Java solution

matched/original
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (int i = 0; i < m; i++) {
            dfs(i, 0, pacific, heights, directions);
            dfs(i, n - 1, atlantic, heights, directions);
        }
        for (int j = 0; j < n; j++) {
            dfs(0, j, pacific, heights, directions);
            dfs(m - 1, j, atlantic, heights, directions);
        }
        
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> cell = new ArrayList<>();
                    cell.add(i);
                    cell.add(j);
                    result.add(cell);
                }
            }
        }
        return result;
    }
    
    private void dfs(int r, int c, boolean[][] ocean, int[][] heights, int[][] directions) {
        ocean[r][c] = true;
        for (int[] dir : directions) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nc >= 0 && nr < heights.length && nc < heights[0].length && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(nr, nc, ocean, heights, directions);
            }
        }
    }
}

JavaScript solution

matched/original
function pacificAtlantic(heights) {
    const m = heights.length, n = heights[0].length;
    const pacific = Array.from({ length: m }, () => Array(n).fill(false));
    const atlantic = Array.from({ length: m }, () => Array(n).fill(false));
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    function dfs(r, c, ocean) {
        ocean[r][c] = true;
        for (const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nc >= 0 && nr < m && nc < n && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(nr, nc, ocean);
            }
        }
    }
    
    for (let i = 0; i < m; i++) {
        dfs(i, 0, pacific);
        dfs(i, n - 1, atlantic);
    }
    for (let j = 0; j < n; j++) {
        dfs(0, j, pacific);
        dfs(m - 1, j, atlantic);
    }
    
    const result = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (pacific[i][j] && atlantic[i][j]) {
                result.push([i, j]);
            }
        }
    }
    return result;
}

Python solution

matched/original
def pacificAtlantic(heights):
    m, n = len(heights), len(heights[0])
    pacific = [[False] * n for _ in range(m)]
    atlantic = [[False] * n for _ in range(m)]
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def dfs(r, c, ocean):
        ocean[r][c] = True
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not ocean[nr][nc] and heights[nr][nc] >= heights[r][c]:
                dfs(nr, nc, ocean)
    
    for i in range(m):
        dfs(i, 0, pacific)
        dfs(i, n - 1, atlantic)
    for j in range(n):
        dfs(0, j, pacific)
        dfs(m - 1, j, atlantic)
    
    result = []
    for i in range(m):
        for j in range(n):
            if pacific[i][j] and atlantic[i][j]:
                result.append([i, j])
    return result

Go solution

matched/original
package main

func pacificAtlantic(heights [][]int) [][]int {
    m, n := len(heights), len(heights[0])
    pacific := make([][]bool, m)
    atlantic := make([][]bool, m)
    for i := range pacific {
        pacific[i] = make([]bool, n)
        atlantic[i] = make([]bool, n)
    }
    directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    
    var dfs func(r, c int, ocean [][]bool)
    dfs = func(r, c int, ocean [][]bool) {
        ocean[r][c] = true
        for _, dir := range directions {
            nr, nc := r+dir[0], c+dir[1]
            if nr >= 0 && nc >= 0 && nr < m && nc < n && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c] {
                dfs(nr, nc, ocean)
            }
        }
    }
    
    for i := 0; i < m; i++ {
        dfs(i, 0, pacific)
        dfs(i, n-1, atlantic)
    }
    for j := 0; j < n; j++ {
        dfs(0, j, pacific)
        dfs(m-1, j, atlantic)
    }
    
    result := [][]int{}
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if pacific[i][j] && atlantic[i][j] {
                result = append(result, []int{i, j})
            }
        }
    }
    return result
}

Explanation

Algorithm

Определите две матрицы для отслеживания клеток, из которых вода может течь в Тихий и Атлантический океаны, используя поиск в глубину (DFS) или поиск в ширину (BFS), начиная с границ, примыкающих к каждому океану.

Выполните поиск для каждого океана, обновляя матрицы достижимости.

Соберите координаты клеток, которые могут стекать в оба океана, проверяя пересечение двух матриц достижимости.

😎