水流算法实现求助：双向BFS路径识别错误排查

背景 #

给定x×y维度的矩阵，最左列与最顶行视为西北海洋边界，最右列与最底行视为东南海洋边界。水流从任意边界单元格出发，仅能流入满足「当前单元格高度≥相邻单元格高度」的相邻单元格。若水流抵达起始海洋的对侧边界，则形成有效路径；若水流停滞或未抵达对侧边界，则不属于有效路径。需分别检查两个海洋的所有有效路径，找出路径重叠的单元格数量及坐标。

问题详情 #

使用类BFS的队列实现两个遍历函数，但无法正确标记符合条件的单元格。以西北海洋路径为例：

• 顶行仅起始点6能形成有效路径，需标记该单元格；
• 左列中1无法形成有效路径，20可一路流至16抵达东南海洋，需标记20、19、18、17、16。
  预期标记的单元格为：6、20、19、18、17、16。

现有代码 #

NW Traversal（从首行/首列出发，抵达东南边界时停止） #

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 Traversal（从末行/末列出发，抵达西北边界时停止） #

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

问题排查 #

traverse_nw的核心问题 #

1. visited标记逻辑错误：仅在细胞有后续可流的邻居时才标记为visited，导致SE边界的终点细胞因无后续邻居，无法被标记为visited，进而无法触发reaches_se的标记。
2. 可达状态传播方向颠倒：试图从NW边界往SE方向传播“可达”状态，但实际逻辑应为：若一个细胞可以流向的邻居能到达SE，那么该细胞本身也能到达SE。原代码传播方向相反，导致状态无法正确回溯。
3. 边界细胞判断条件冗余：判断细胞是否在SE边界时附加了visited_nw[i][j]条件，而终点细胞因未被标记visited，无法被识别为可达SE的细胞。

traverse_se的核心问题 #

可达状态未传播：仅将NW边界的细胞标记为reaches_nw=True，未将该状态传播到那些可以流向NW边界细胞的中间细胞，导致无法正确标记所有从SE出发能到达NW的路径。

修正后的代码 #

修正后的NW Traversal #

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)]

    # 第一步：正向BFS，遍历所有从NW边界出发能到达的细胞（水流方向：当前≥邻居）
    queue = deque()
    # 初始化NW边界所有细胞
    for j in range(max_j + 1):
        visited_nw[0][j] = True
        queue.append((0, j))
    for i in range(1, max_i + 1):
        visited_nw[i][0] = True
        queue.append((i, 0))
    
    while queue:
        i, j = queue.popleft()
        # 遍历四个方向的邻居
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni <= max_i and 0 <= nj <= max_j:
                if not visited_nw[ni][nj] and table[i][j] >= table[ni][nj]:
                    visited_nw[ni][nj] = True
                    queue.append((ni, nj))
    
    # 第二步：反向BFS，标记所有能到达SE边界的细胞（从SE边界的已访问细胞回溯）
    queue = deque()
    # 初始化SE边界中属于NW可达路径的细胞
    for j in range(max_j + 1):
        if visited_nw[max_i][j]:
            reaches_se[max_i][j] = True
            queue.append((max_i, j))
    for i in range(max_i):
        if visited_nw[i][max_j]:
            reaches_se[i][max_j] = True
            queue.append((i, max_j))
    
    while queue:
        i, j = queue.popleft()
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni <= max_i and 0 <= nj <= max_j:
                # 反向条件：当前细胞是ni,nj的下游，ni,nj可以流到当前细胞，且ni,nj在NW可达路径中
                if visited_nw[ni][nj] and not reaches_se[ni][nj] and table[ni][nj] >= table[i][j]:
                    reaches_se[ni][nj] = True
                    queue.append((ni, nj))
    
    return visited_nw, reaches_se

修正后的SE Traversal #

def traverse_se(table):
    max_i = len(table) - 1
    max_j = len(table[0]) - 1
    visited_se = [[False for _ in range(max_j + 1)] for _ in range(max_i + 1)]
    reaches_nw = [[False for _ in range(max_j + 1)] for _ in range(max_i + 1)]

    # 第一步：正向BFS，遍历所有从SE边界出发能到达的细胞（水流方向：当前≥邻居）
    queue = deque()
    # 初始化SE边界所有细胞
    for j in range(max_j + 1):
        visited_se[max_i][j] = True
        queue.append((max_i, j))
    for i in range(max_i):
        visited_se[i][max_j] = True
        queue.append((i, max_j))
    
    while queue:
        i, j = queue.popleft()
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni <= max_i and 0 <= nj <= max_j:
                if not visited_se[ni][nj] and table[i][j] >= table[ni][nj]:
                    visited_se[ni][nj] = True
                    queue.append((ni, nj))
    
    # 第二步：反向BFS，标记所有能到达NW边界的细胞（从NW边界的已访问细胞回溯）
    queue = deque()
    # 初始化NW边界中属于SE可达路径的细胞
    for j in range(max_j + 1):
        if visited_se[0][j]:
            reaches_nw[0][j] = True
            queue.append((0, j))
    for i in range(1, max_i + 1):
        if visited_se[i][0]:
            reaches_nw[i][0] = True
            queue.append((i, 0))
    
    while queue:
        i, j = queue.popleft()
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni <= max_i and 0 <= nj <= max_j:
                # 反向条件：当前细胞是ni,nj的下游，ni,nj可以流到当前细胞，且ni,nj在SE可达路径中
                if visited_se[ni][nj] and not reaches_nw[ni][nj] and table[ni][nj] >= table[i][j]:
                    reaches_nw[ni][nj] = True
                    queue.append((ni, nj))
    
    return visited_se, reaches_nw

修正逻辑说明 #

采用两步BFS的方式确保有效路径标记准确：

1. 正向BFS：从起始边界（NW/SE）出发，遍历所有水流能到达的细胞，标记为已访问，确保覆盖所有可能的路径范围。
2. 反向BFS：从对侧边界（SE/NW）中属于已访问集合的细胞出发，反向回溯所有可以流向这些细胞的前置细胞，标记这些细胞为“可达对侧边界”的有效路径细胞，确保所有能抵达对侧边界的细胞都被正确标记。

内容的提问来源于stack exchange，提问作者Cristii