:orphan:

Pacific Atlantic Water Flow
===========================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/pacific-atlantic-water-flow/

There is an ``m x n`` rectangular island that borders both the
**Pacific Ocean** and **Atlantic Ocean**. The **Pacific Ocean** touches
the island's left and top edges, and the **Atlantic Ocean** touches the
island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an
``m x n`` integer matrix ``heights`` where ``heights[r][c]`` represents
the **height above sea level** of the cell at coordinate ``(r, c)``.

The island receives a lot of rain, and the rain water can flow to
neighboring cells directly north, south, east, and west if the
neighboring cell's height is **less than or equal to** the current
cell's height. Water can flow from any cell adjacent to an ocean into
the ocean.

Return *a 2D list of grid coordinates* ``result`` *where*
``result[i] = [r``\ :sub:`i`\ ``, c``\ :sub:`i`\ ``]`` *denotes that
rain water can flow from cell* ``(r``\ :sub:`i`\ ``,
c``\ :sub:`i`\ ``)`` *to* **both** *the Pacific and Atlantic oceans*.



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

**Example 2:**

::

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



**Constraints:**

- ``m == heights.length``
- ``n == heights[r].length``
- ``1 <= m, n <= 200``
- ``0 <= heights[r][c] <= 10``\ :sup:`5`

.. highlight:: python

Pattern
-------
Graph, DFS, Matrix

Approaches
----------

.. tab-set::

    .. tab-item:: DFS

        **Code**

        .. literalinclude:: ../problems/medium/pacific-atlantic-water-flow/pacific_atlantic_water_flow__dfs.py
            :language: python
            :lines: 10-

        **Test**

        >>> from pacific_atlantic_water_flow__dfs import pacificAtlantic
        >>> pacificAtlantic([[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]])
        [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
        >>> pacificAtlantic([[1]])
        [[0, 0]]

        .. autofunction:: pacific_atlantic_water_flow__dfs.pacificAtlantic