Не могу понять алгоритм движения воды. ⇐ Python

[Anonymous]

Контекст:

У меня есть матрица x и y размеры.
Самый левый столбец и самая верхняя строка считаются границами Северо-Западного океана.
Крайний правый столбец и самая нижняя строка считаются краями Юго-Восточного океана.
Начиная с любого квадрата, с любого края вода будет перетекать только в соседние квадраты. if:

текущий квадрат воды >= соседний квадрат

Если вода достигает одного из краев океана, противоположного начальному, она образует путь.
Если вода застревает и не может никуда уйти или не достигает одного из противоположных краев, это НЕ путь.
Что мне нужно сделать, это проверить каждый путь для каждого океана, а затем перекрыть их и указать общее количество перекрывающихся квадратов и их координаты.

Лично я подошел к этому, думая об этом как о карте высот.
Я сделал 2 функции, используя очередь и что-то вроде поиска BFS. У меня проблема в том, что я не могу выделить точные правильные квадраты для выделения


Это матрица, которая вызывает у меня проблемы.
На пути NW:
Верхний ряд: если начальная точка отличается от 6, это не сработает из-за большего количества людей вокруг. 6 будет выделено
Левый столбец: 1 не работает, а 20 работает, и это может привести к тому, что 16 достигнет юго-восточного океана. Допустимый путь.
Таким образом, выделенные квадраты должны быть:
6, 20, 19. >, 18, 17, 16.
Обход по северо-западу (начать с первого строку или первый столбец и останавливаться только в том случае, если она достигает юго-восточного края)

Код: Выделить всё

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 (начинается с последней строки или последнего столбца и останавливается только при достижении северо-западного края)

Код: Выделить всё

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

Если у вас есть что-нибудь, дайте мне знать, заранее спасибо


Подробнее здесь: https://stackoverflow.com/questions/790 ... -algorithm