417. 태평양 대서양 수류

설명

태평양과 대서양 모두에 접해 있는 m x n 직사각형 섬이 있습니다. 태평양은 섬의 왼쪽과 위쪽 가장자리에 닿고 대서양은 섬의 오른쪽과 아래쪽 가장자리에 닿습니다.

섬은 정사각형 셀의 그리드로 분할됩니다. m x n 정수 행렬heights 여기서 heights[r][c] 좌표(r, c)에서 셀의 해발 높이를 나타냅니다.

섬은 많은 양의 비를 받고 있으며 이웃 셀의 높이가 현재 셀의 높이보다 작거나 같으면 빗물이 이웃 셀로 바로 북쪽, 남쪽, 동쪽 및 서쪽으로 흐를 수 있습니다. 물은 바다에 인접한 모든 셀에서 바다로 흐를 수 있습니다.

그리드 좌표의 2D 목록result을 반환합니다. 여기서 result[i] = [ri, ci]는 빗물이 셀(ri, ci)에서 태평양과 대서양 모두로 흐를 수 있음을 나타냅니다.

예 1:

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]]

예 2:

Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]

제약:

m == heights.length

n == heights[r].length

1 <= m, n <= 200

0 <= heights[r][c] <= $10^5$

솔루션

솔루션 1

직관

바다에서 육지로heights[x][y] <= heights[dx][dy]
두 가지 유형의 플래그, 1과 2, 두 대양이 동시에 육지에 도달할 수 있는 경우 플래그는 3입니다.

암호

class Solution {
private:
    int m, n;
    int dirs[5] = { 0, 1, 0, -1, 0 };
    vector<vector<int>> state;
    void dfs(int x, int y, int val, vector<vector<int>>& heights) {
        if (state[x][y] & val) return;
        state[x][y] |= val;
        for (int i = 0; i < 4; i++) {
            int dx = x + dirs[i], dy = y + dirs[i + 1];

            if (dx >= 0 && dx < m && dy >= 0 && dy < n && heights[x][y] <= heights[dx][dy]) {
                dfs(dx, dy, val, heights);
            }
        }
    }

public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(), n = heights[0].size();
        state.resize(m, vector<int>(n, 0));
        // top
        for (int i = 0; i < n; i++) dfs(0, i, 1, heights);
        // left
        for (int i = 0; i < m; i++) dfs(i, 0, 1, heights);
        // bottom
        for (int i = 0; i < n; i++) dfs(m - 1, i, 2, heights);
        // right
        for (int i = 0; i < m; i++) dfs(i, n - 1, 2, heights);

        vector<vector<int>> res;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (state[i][j] == 3) res.push_back({ i,j });
            }
        }
        return res;
    }
};

복잡성

시간: O(n)

스페이스: O(n)