2D matrix containing only 0s and 1s - python

Question

With a given 2D matrix containing only 0s and 1s. Each 0 represents land, and each 1 represents part of a river. A river consists of any number of 1s that are either horizontally or vertically adjacent (but not diagonally adjacent). The number of adjacent 1s forming a river determine its size. Write a function that returns an array of the sizes of all rivers represented in the input matrix.

   Input:
array =[
        [0, 0, 1, 0, 1, 0],
        [1, 0, 0, 1, 1, 0],
        [1, 0, 0, 0, 0, 1],
        [1, 0, 0, 1, 1, 1],
    ]
output:
There are 4 rivers in the given matrix, and their sizes are: [1, 3, 3, 4]

but actually im expecting to have: [1, 2, 2, 2, 3, 3]

because im looking for only rivers which are horizontally or vertically adjacent but not a river which is both. (as my algorith output brings).

MY algorithm uses DFS:

def riverSizes(matrix):
    sizes = []  # # It would contain all of our river sizes
    visited = [[False for value in row] for row in matrix]
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if visited[i][j]:
                continue
            traverseNode(i, j, matrix, visited, sizes)
    return sizes


def traverseNode(i, j, matrix, visited, sizes):
    currentRiverSize = 0
    nodesToExplore = [[i, j]]
    while len(nodesToExplore):
        currentNode = nodesToExplore.pop()
        i = currentNode[0]
        j = currentNode[1]
        if visited[i][j]:
            continue
        visited[i][j] = True
        if matrix[i][j] == 0:
            continue
        currentRiverSize += 1
        unvisitedNeighbors = getUnvisitedNeighbors(i, j, matrix, visited)
        for neighbor in unvisitedNeighbors:
            nodesToExplore.append(neighbor)
    if currentRiverSize > 0:
        sizes.append(currentRiverSize)


def getUnvisitedNeighbors(i, j, matrix, visited):
    unvisitedNeighbors = []
    if i > 0 and not visited[i - 1][j]:
        unvisitedNeighbors.append([i - 1, j])
    if i < len(matrix) - 1 and not visited[i + 1][j]:
        unvisitedNeighbors.append([i + 1, j])
    if j > 0 and not visited[i][j - 1]:
        unvisitedNeighbors.append([i, j - 1])
    if j < len(matrix[0]) - 1 and not visited[i][j + 1]:
        unvisitedNeighbors.append([i, j + 1])
    return unvisitedNeighbors

how can i fix it?

Answer 1

The algorithm is giving you the right result for the problem [1, 3, 3, 4].
A river is composed of 1's that are horizontally or vertically adjacent to each other (a 1 can not be horizontally and vertically adjacent to another 1 at the same time, in the case the confusion is the 'either' 'or' of the problem statement)).

That is why getUnvisitedNeighbors() looks into all vertical and horizontal directions from a field containing a 1.
In other words, a river could have an L shape resulting matrix