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

😎 Решение:

func pacificAtlantic(_ heights: [[Int]]) -> [[Int]] {
    let m = heights.count
    let n = heights[0].count
    var pacific = Array(repeating: Array(repeating: false, count: n), count: m)
    var atlantic = Array(repeating: Array(repeating: false, count: n), count: m)
    let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    func dfs(_ r: Int, _ c: Int, _ ocean: inout [[Bool]]) {
        ocean[r][c] = true
        for (dr, dc) in directions {
            let 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 i in 0..<m {
        dfs(i, 0, &pacific)
        dfs(i, n - 1, &atlantic)
    }
    for j in 0..<n {
        dfs(0, j, &pacific)
        dfs(m - 1, j, &atlantic)
    }
    
    var result = [[Int]]()
    for i in 0..<m {
        for j in 0..<n {
            if pacific[i][j] && atlantic[i][j] {
                result.append([i, j])
            }
        }
    }
    return result
}

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