[LeetCode刷題筆記] 417 – Pacific Atlantic Water Flow

題目描述：

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

The order of returned grid coordinates does not matter.
Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

一刷題解（DFS）：

對於這類二維數組搜索的題，一般思路都是DFS，但是應該如何DFS呢？我最開始是打算對每個點進行檢查，看看它們可否既有路徑通往太平洋，又有路徑前往大西洋，但是這樣做時間複雜度會爆炸。

最後去看了一下討論區大神的做法，發現他們的思路雖然也是DFS，但是他們是從海洋的邊界出發，並對每個海洋用一個bool[,]記錄各自的海域，如果前一格的水位比當前水位要低，那就代表當前水位可以流去前一格，也就是當前位置跟前一格是同一個水域，然後把bool[當前位置行坐標, 當前位置列坐標]設置為true。

最後，把太平洋和大西洋的水域都標記好之後，這兩個水域的bool[,]中共同為true的部分，就代表了這些格子同為兩個水域的一部分，水也可以從這些格子開始，既流向太平洋和大西洋。

下面是這個DFS思路的實現代碼：

public class Solution {
    public IList<IList<int>> PacificAtlantic(int[][] matrix) {
        List<IList<int>> res = new List<IList<int>>();

        if(matrix.Length == 0 || matrix[0].Length == 0){ return res; }
        
        //標記水域的bool二維數組
        bool[,] pacificFlow = new bool[matrix.Length, matrix[0].Length];
        bool[,] atlanticFlow = new bool[matrix.Length, matrix[0].Length];

        for (int i = 0; i < matrix.Length; i++)
        {
            for (int j = 0; j < matrix[0].Length; j++)
            {
                //Pacific
                if (i == 0 || j == 0)
                {
                    CheckFlow(matrix, int.MinValue, (i, j), pacificFlow);
                }

                //Atlantic
                if (i == matrix.Length - 1 || j == matrix[0].Length - 1)
                {
                    CheckFlow(matrix, int.MinValue, (i, j), atlanticFlow);
                }
            }
        }

        //找出兩個水域的共通處
        for (int i = 0; i < matrix.Length; i++)
        {
            for (int j = 0; j < matrix[0].Length; j++)
            {
                if (pacificFlow[i, j] && atlanticFlow[i, j])
                {
                    res.Add(new List<int>() { i, j });
                }
            }
        }
        return res;       
    }

    void CheckFlow(int[][] matrix, int prevHeight, (int r, int c)pos, bool[,] flow)
    {
        //邊界檢查
        if(pos.r >= matrix.Length || pos.r < 0 || pos.c >= matrix[0].Length || pos.c < 0)
        {
            return;
        }
        
        //如果該格子已被標記過為當前水域的一部分，就跳過
        if (flow[pos.r, pos.c]) { return; }
             
        //上個格子的水位比當前格子水位高，意味當前格子不能把水流向上個格子
        if(prevHeight > matrix[pos.r][pos.c]) { return; }
        //標記當前格子為當前水域的一部分
        flow[pos.r, pos.c] = true;

        //向當前格子的四個方向DFS
        CheckFlow(matrix, matrix[pos.r][pos.c], (pos.r + 1, pos.c), flow);
        CheckFlow(matrix, matrix[pos.r][pos.c], (pos.r - 1, pos.c), flow);
        CheckFlow(matrix, matrix[pos.r][pos.c], (pos.r, pos.c + 1), flow);
        CheckFlow(matrix, matrix[pos.r][pos.c], (pos.r, pos.c - 1), flow);
    }
}