Задача: 417. Pacific Atlantic Water Flow
Сложность: medium

Имеется прямоугольный остров размером 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]]

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

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);
            }
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний