Задача: 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⃣Соберите координаты клеток, которые могут стекать в оба океана, проверяя пересечение двух матриц достижимости.

😎 Решение:

function pacificAtlantic($heights) {
    $m = count($heights);
    $n = count($heights[0]);
    $pacific = array_fill(0, $m, array_fill(0, $n, false));
    $atlantic = array_fill(0, $m, array_fill(0, $n, false));
    $directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    function dfs($r, $c, &$ocean, $heights, $directions) {
        $ocean[$r][$c] = true;
        foreach ($directions as [$dr, $dc]) {
            $nr = $r + $dr;
            $nc = $c + $dc;
            if ($nr >= 0 && $nc >= 0 && $nr < count($heights) && $nc < count($heights[0]) && !$ocean[$nr][$nc] && $heights[$nr][$nc] >= $heights[$r][$c]) {
                dfs($nr, $nc, $ocean, $heights, $directions);
            }
        }
    }
    
    for ($i = 0; $i < $m; $i++) {
        dfs($i, 0, $pacific, $heights, $directions);
        dfs($i, $n - 1, $atlantic, $heights, $directions);
    }
    for ($j = 0; $j < $n; $j++) {
        dfs(0, $j, $pacific, $heights, $directions);
        dfs($m - 1, $j, $atlantic, $heights, $directions);
    }
    
    $result = [];
    for ($i = 0; $i < $m; $i++) {
        for ($j = 0; $j < $n; $j++) {
            if ($pacific[$i][$j] && $atlantic[$i][$j]) {
                $result[] = [$i, $j];
            }
        }
    }
    return $result;
}

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