資訊專欄INFORMATION COLUMN
摘要：題目要求假設(shè)左上角的所有周圍面積為太平洋，右下角的所有面積為大西洋。假定水只能從高出流向低處，要求找出所有既可以流向太平洋也可以流向大西洋的水域。但是反過來來看，任意一個(gè)可以到達(dá)大西洋的水流必然會(huì)抵達(dá)數(shù)組左邊和上邊的任意一點(diǎn)。
題目要求
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).
假設(shè)左上角的所有周圍面積為太平洋，右下角的所有面積為大西洋。現(xiàn)在使用數(shù)組來表示一大片水域，其中數(shù)組的每一個(gè)位置上的元素代表某一個(gè)小水域的高度。假定水只能從高出流向低處，要求找出所有既可以流向太平洋也可以流向大西洋的水域。
思路和代碼首先需要理解題意，題目中強(qiáng)調(diào)了水流可以涌向上下左右四個(gè)方向，即水流并非只能一直往左流或是一直往上流才能達(dá)到太平洋，它可以繞著圈子轉(zhuǎn)，如下面的例子所示：
{1,2,3},
{8,9,4},
{7,6,5}
高度為6的水域的水可以由6->5->4并最終匯入太平洋
這道題目直觀上來看是需要以數(shù)組中的任意一個(gè)位置為起點(diǎn)，分別尋找一條數(shù)字由大到小并最終到達(dá)左上側(cè)或是右下側(cè)的路徑。但是反過來來看，任意一個(gè)可以到達(dá)大西洋的水流必然會(huì)抵達(dá)數(shù)組左邊和上邊的任意一點(diǎn)。因此，我們可以以數(shù)組的邊緣作為起點(diǎn)，尋找所有數(shù)字由小到大的路徑，該路徑上的所有點(diǎn)必然可以到達(dá)該邊所在的洋流。
這里可以采用深度優(yōu)先搜索或是廣度優(yōu)先搜索的方式遍歷所有的可達(dá)水域。停止延伸的條件就是遇到已經(jīng)訪問過的水域或者該水域的高度低于前置水域高度。
代碼如下：
