2. Leetcode Algorithm Notes - Pacific Atlantic Water Flow Problem, Depth-First Search

发表于 更新于 分类于 本文字数： 826 阅读时长 ≈ 3 分钟

This is still an algorithm note, this time recording the Pacific Atlantic Water Flow Problem on Leetcode last Wednesday (April 27th). The algorithm note is organized based on the official solution, which uses depth-first traversal. Yesterday, I finally encountered a difficult problem (my first reaction: I’m screwed, my streak is going to be broken), but if you pay attention to the details, you can still solve it. For example, <A></A><B></B> is not valid, although it seems valid in HTML, it is because the browser has added <html></html> for us, so it is valid.(English version Translated by GPT-3.5, 返回中文)

Original Problem

Original problem link: 417. Pacific Atlantic Water Flow - Leetcode

image-20220503110410488

In-depth Understanding

When I first started working on this problem, I didn’t have a clue (I found that I would get confused when it comes to depth-first traversal, I just get dizzy when I see it going back and forth), but everything lacks a clue. Once you have a clue, you have half of the problem solved. As a medium-level problem, this problem requires finding the water flow that flows into both the Pacific and Atlantic. We can actually solve it as follows (based on the official solution): first calculate the water flow from the Pacific to the Atlantic, then calculate the water flow from the Atlantic to the Pacific, and finally find the intersection of the two arrays. Break it down as follows:

  1. First, we need to define two arrays to store the water flow from the Pacific to the Atlantic and the water flow from the Atlantic to the Pacific.
  2. Then, build 4 loops to recursively calculate the water flow from the Pacific to the Atlantic horizontally, the water flow from the Pacific to the Atlantic vertically, and the water flow from the Atlantic to the Pacific horizontally and vertically.
  3. Finally, merge the parts of the two arrays that have the same flow direction.
  4. In the recursion, constantly check and recursively determine which direction (up, down, left, right) the “mountain” can flow to the other side, and also determine whether the rocks in these directions are higher. If they are higher, recursively determine where the higher rock can flow to.

Coding Begins

  1. First, define several variables to record the row, column, and height.
1
2
rows = len(matrix)
cols = len(matrix[0])
  1. Then, define two arrays to record the water flow from the Pacific to the Atlantic and from the Atlantic to the Pacific.
1
2
pacific = [[False] * cols for _ in range(rows)]
atlantic = [[False] * cols for _ in range(rows)]
  1. Build four loops to recursively determine the water flow from the Pacific and Atlantic to each other.
1
2
3
4
5
6
7
for row in range(rows):
    dfs(row, 0, matrix, pacific)
    dfs(row, cols - 1, matrix, atlantic)

for col in range(cols):
    dfs(0, col, matrix, pacific)
    dfs(rows - 1, col, matrix, atlantic)
  1. Then, merge the results.
1
2
3
4
5
6
7
8
9
10
11
12
13
result = []
for row in range(rows):
    for col in range(cols):
        if pacific[row][col] and atlantic[row][col]:
            result.append([row, col])
```  

   ![Merge Result](https://file.ruterfu.com/image/2022/05/03/AKMaEuHEtyDxEvDEnA/IHy5y6CpC9CvAAoG-medium.jpg)

5. Finally, write the relevant recursion code. Here, we need to define a value, `direction`, which can actually be moved to a member variable.

```python
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
  1. Then, determine the water flow direction in each direction.
1
2
3
4
5
6
7
def dfs(row, col, matrix, ocean):
    ocean[row][col] = True
    for direction in directions:
        newRow, newCol = row + direction[0], col + direction[1]
        if newRow < 0 or newRow >= rows or newCol < 0 or newCol >= cols or ocean[newRow][newCol] or matrix[newRow][newCol] < matrix[row][col]:
            continue
        dfs(newRow, newCol, matrix, ocean)

Simulation Process

Complete Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def pacificAtlantic(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    
    pacific = [[False] * cols for _ in range(rows)]
    atlantic = [[False] * cols for _ in range(rows)]
    
    for row in range(rows):
        dfs(row, 0, matrix, pacific)
        dfs(row, cols - 1, matrix, atlantic)
        
    for col in range(cols):
        dfs(0, col, matrix, pacific)
        dfs(rows - 1, col, matrix, atlantic)
        
    result = []
    for row in range(rows):
        for col in range(cols):
            if pacific[row][col] and atlantic[row][col]:
                result.append([row, col])
    
    return result

directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

def dfs(row, col, matrix, ocean):
    ocean[row][col] = True
    for direction in directions:
        newRow, newCol = row + direction[0], col + direction[1]
        if newRow < 0 or newRow >= rows or newCol < 0 or newCol >= cols or ocean[newRow][newCol] or matrix[newRow][newCol] < matrix[row][col]:
            continue
        dfs(newRow, newCol, matrix, ocean)