coding

LeetCode daily challenge (2022/08/31)

417. Pacific Atlantic Water Flow

連續五天都是 matrix 相關的問題啊…

這題一開始就決定用深度優先搜尋配合遞迴的解法，使用正向搜尋的邏輯，也就是題目所說的：假如 heights(x, y) >= heights(x + 1, y) ，河流就可以往 x + 1 的方向流動，結果發現處理重複尋訪的問題實在很煩人，空間複雜度平白多了 O(m*n) 不說，程式邏輯也是奇醜無比，後來靈光一閃，其實可以用反向搜尋，也就是從岸邊開始往內陸尋找上游，這樣就可以完全無視重複尋訪的問題，有點 DP 的感覺…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void flow(vector<vector<int>>& h, vector<vector<bool>>& t, int row, int col) {
    if(row < 0 || row > m - 1 || col < 0 || col > n - 1) return;
    if (!t[row][col]) {
        t[row][col] = true;

        if (row - 1 >= 0 && h[row][col] <= h[row - 1][col]) flow(h, t, row - 1, col);
        if (col - 1 >= 0 && h[row][col] <= h[row][col - 1]) flow(h, t, row, col - 1);
        if (row + 1 < m && h[row][col] <= h[row + 1][col]) flow(h, t, row + 1, col);
        if (col + 1 < n && h[row][col] <= h[row][col + 1]) flow(h, t, row, col + 1);
    }
}

可以看到規則變成 heights(x, y) <= heights(x + 1, y) 才繼續往 x + 1 的方向走，反正就是一路往上，如果已經是 true 就直接離開，否則先標記成 true 再繼續溯源。這裡的參數 h 就是原始題目輸入的 heights ， t 則是表示座標 (x, y) 可否流至 Pacific Ocean 或是 Atlantic Ocean 的布林陣列，遞迴的起點就是從岸邊開始

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

static int m, n;

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    m = heights.size(), n = heights[0].size();
    vector<vector<bool>> toPac(m, vector<bool>(n, false));
    vector<vector<bool>> toAtl(m, vector<bool>(n, false));
    vector<vector<int>> ans;

    for (int p = 0; p < m; p++)
        for (int q = 0; q < n; q++) {
            if (p == m - 1 || q == n - 1)
                flow(heights, toAtl, p, q);
            if (p == 0 || q == 0)
                flow(heights, toPac, p, q);
        }

    for (int x = 0; x < m; x++)
        for (int y = 0; y < n; y++)
            if (toPac[x][y] && toAtl[x][y])
                ans.push_back({ x, y });

    return ans;
}

因為 Pacific Ocean 是在西北方，所以岸邊座標就是 row = 0 和 column = 0 ，而 Atlantic Ocean 是在東南方，所以從 row = m - 1 和 column = n - 1 的位置開始遞迴，最後找出兩個矩陣的交集就是答案了

comments powered by Disqus