想不出水流算法

Question

---

背景：

---

我有一个 x 和 y 维度的矩阵。

最左边的列和最上面的行被认为是西北海洋的边缘。

最右边的列和最底下的行被认为是东南海洋的边缘。

从任何方格开始，在任何边缘，只有满足以下条件，水才会流入相邻的方格：

当前水域方格 >= 相邻方格

如果水到达相对海洋的边缘之一而不是起始位置，则会形成一条路径。

如果水被卡住而无法流到任何地方，或者没有到达相对的边缘之一，则它不是路径。

我需要做的是检查每个海洋的每条路径，然后将它们重叠并给出重叠方块的总数及其坐标。

---

就我个人而言，我已经接近这一点，将其视为高度图。 我创建了 2 个函数，使用队列和 BFS 搜索。我遇到的问题是，我似乎无法获得确切正确的方块来突出显示

这是给我带来问题的矩阵。

在西北路径上： 顶行：如果起始点不是 6，则由于周围的数字更大，它将不起作用。 6 将突出显示

左栏：1 不起作用，但 20 起作用，并且可以一直到 16 到达东南海洋。有效路径。

所以突出显示的方块应该是： 6、20、19、18、17、16。

NW 遍历（从第一行或第一列开始，到达 SE 边缘才停止）

from collections import deque

def traverse_nw(table):
    max_i = len(table) - 1
    max_j = len(table[0]) - 1
    visited_nw = [[False for _ in range(max_j + 1)] for _ in range(max_i + 1)]
    reaches_se = [[False for _ in range(max_j + 1)] for _ in range(max_i + 1)]  # Track paths reaching SE

    # Initialize queue with all cells in the first row and first column (NW ocean)
    queue = deque([(0, j) for j in range(max_j + 1)] + [(i, 0) for i in range(1, max_i + 1)])

    while queue:
        i, j = queue.popleft()

        if visited_nw[i][j]:
            continue
        
        # Move to neighbors if their height is lower or equal
        valid_neighbors = []
        if i > 0 and not visited_nw[i - 1][j] and table[i][j] >= table[i - 1][j]:  # Up
            valid_neighbors.append((i - 1, j))
        if i < max_i and not visited_nw[i + 1][j] and table[i][j] >= table[i + 1][j]:  # Down
            valid_neighbors.append((i + 1, j))
        if j > 0 and not visited_nw[i][j - 1] and table[i][j] >= table[i][j - 1]:  # Left
            valid_neighbors.append((i, j - 1))
        if j < max_j and not visited_nw[i][j + 1] and table[i][j] >= table[i][j + 1]:  # Right
            valid_neighbors.append((i, j + 1))

        # Only mark a cell as visited if it has valid neighbors
        if valid_neighbors:
            visited_nw[i][j] = True

        # Check if the current cell has reached the SE edge (bottom row or rightmost column)
        if (i == max_i or j == max_j) and visited_nw[i][j]:
            reaches_se[i][j] = True  # This path reaches the SE edge

        # Only proceed to mark a cell as leading to SE if one of its valid neighbors leads to SE
        for ni, nj in valid_neighbors:
            queue.append((ni, nj))
            if reaches_se[i][j]:  # If the current cell can reach SE, propagate that information
                reaches_se[ni][nj] = True

    return visited_nw, reaches_se

SE 遍历（从最后一行或最后一列开始，到达 NW 边缘才停止）

def traverse_se(table):
    max_i = len(table) - 1
    max_j = len(table[0]) - 1
    
    # Create a grid to track visited cells for SE traversal
    visited_se = [[False for _ in range(max_j + 1)] for _ in range(max_i + 1)]
    
    # Initialize queue with all cells in the last row and last column (SE ocean)
    queue = deque([(max_i, j) for j in range(max_j + 1)] + [(i, max_j) for i in range(max_i)])

    # Create a grid to mark paths that can reach the NW ocean
    reaches_nw = [[False for _ in range(max_j + 1)] for _ in range(max_i + 1)]

    # BFS to explore SE traversal
    while queue:
        i, j = queue.popleft()

        # If the cell is already visited, skip it
        if visited_se[i][j]:
            continue

        # Mark the cell as visited
        visited_se[i][j] = True

        # Check if the current cell has reached the NW edge (top row or leftmost column)
        if i == 0 or j == 0:
            reaches_nw[i][j] = True  # This path reaches the NW ocean

        # Move to neighboring cells if their height is lower or equal
        if i > 0 and not visited_se[i - 1][j] and table[i][j] >= table[i - 1][j]:  # Up
            queue.append((i - 1, j))
        if i < max_i and not visited_se[i + 1][j] and table[i][j] >= table[i + 1][j]:  # Down
            queue.append((i + 1, j))
        if j > 0 and not visited_se[i][j - 1] and table[i][j] >= table[i][j - 1]:  # Left
            queue.append((i, j - 1))
        if j < max_j and not visited_se[i][j + 1] and table[i][j] >= table[i][j + 1]:  # Right
            queue.append((i, j + 1))

    return visited_se, reaches_nw

如果您有任何事情请告诉我，提前谢谢

Answer 1

我认为递归 DFS 方法更容易：

table = [[1,2,3,4,5,6], [20,21,22,23,24,7], [19,32,33,34,25,8], [18,31,36,35,26,9],[17,30,29,28,27,10], [16,15,14,13,12,11]]
visited = [[False for _ in range(6)] for _ in range(6)]
reaches_se = [[False for _ in range(6)] for _ in range(6)]


for coord in ([(0, j) for j in range(6)] + [(i, 0) for i in range(1,6)]):
    reached_condition(coord, is_SE)

print(reaches_se)


def reached_condition(coord, condition):
    (i, j) = coord
    if visited[i][j]:
        return reaches_se[i][j]
    
    reached = False
    if condition(coord): reached = True
    
    valid_neighbors = get_valid_neighbors(coord)
    for coord_n in valid_neighbors:
        if reached_condition(coord_n, condition): reached = True
    
    if reached: reaches_se[i][j] = True;
    visited[i][j] = True
    return reached
    
def get_valid_neighbors(coord):
    (i, j) = coord
    valid_neighbors = []
    if i > 0 and table[i][j] >= table[i - 1][j]:  # Up
        valid_neighbors.append((i - 1, j))
    if i < 5 and table[i][j] >= table[i + 1][j]:  # Down
        valid_neighbors.append((i + 1, j))
    if j > 0 and table[i][j] >= table[i][j - 1]:  # Left
        valid_neighbors.append((i, j - 1))
    if j < 5 and table[i][j] >= table[i][j + 1]:  # Right
        valid_neighbors.append((i, j + 1))
    return valid_neighbors

def is_NW(coord):
    (i, j) = coord
    if i == 0 or j == 0: return True
    else: return False


def is_SE(coord):
    (i, j) = coord
    if i == 5 or j == 5: return True
    else: return False