Context:
I have a matrix of x and y dimensions.
The left-most column and the top-most row are considered the edges of the North-West ocean.
The right-most column and the bottom-most row are considered the edges of the South-East ocean.
Starting from any square, on any edge, the water will flow into adjacent squares only if:
current square of water >= neighbor square
If the water reaches one of the edges of the opposite ocean than the starting one, it forms a path.
If the water gets stuck and can't go anywhere, or if it doesn't reach one of the opposite edges, it is NOT a path.
What I need to do is check each path, for each ocean and then overlap them and give the total number of overlapping squares and their coordinates.
Personally, I have approached this, thinking of it like a height map.
I have made 2 functions, using a queue and sort-of a BFS search. The problem I have is, I cannot seem to get the exact correct squares to highlight
This is the matrix that is giving me problems.
On the NW path: Top row: If the starting point is anything other than 6, it won't work cause of higher numbers around. 6 will be highlighted
Left column: 1 does not work, but 20 does, and it can take it all the way to 16 reaching the SE ocean. Valid path.
So the highlighted squares should be: 6, 20, 19, 18, 17, 16.
NW Traversal (start from the first row or first column and stop only if it reaches the SE edge)
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 (start from the last row or last column and stop only if it reaches the NW edge)
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
If you got anything let me know, thanks in advance
