I have the following recursiv function in python:

def _floodfill(matrix, x, y, counter):
    if matrix[x][y] != 9:
        matrix[x][y] = 9
        counter  = 1
        # recursively invoke flood fill on all surrounding cells:
        if x > 0:
            counter  = int(_floodfill(matrix, x - 1, y, counter) or 0)
        if x < len(matrix) - 1:
            counter  = int(_floodfill(matrix, x   1, y, counter) or 0)
        if y > 0:
            counter  = int(_floodfill(matrix, x, y - 1, counter) or 0)
        if y < len(matrix[0]) - 1:
            counter  = int(_floodfill(matrix, x, y   1, counter) or 0)
        return counter

I want to count how often this function is called respectively count how many numbers are != 9 in the region. Using he following matrix and invocing the function like: _floodfill(matrix,1,1,0) the function should return 2:

[[9,9,9],
 [9,2,9],
 [9,3,9],
 [9,9,9]]

what's the problem with my code?

EDIT I think the function is more readable like this:

def _floodfill(matrix, x, y, counter):
    if matrix[x][y] != 9:
        matrix[x][y] = 9
        counter  = 1
        # recursively invoke flood fill on all surrounding cells:
        if x > 0:
            counter  = _floodfill(matrix, x - 1, y, counter)
        if x < len(matrix) - 1:
            counter  = _floodfill(matrix, x   1, y, counter)
        if y > 0:
            counter  = _floodfill(matrix, x, y - 1, counter)
        if y < len(matrix[0]) - 1:
            counter  = _floodfill(matrix, x, y   1, counter)
        return counter
    else:
        return 0

CodePudding user response：

Three remarks:

1. You don't need to pass counter down to your recursive calls. What would they need it for? counter holds the number of cells previously visited. Your recursive calls don't need to know how many cells you have already visited. That information moves the other way around: what you want is for your recursive calls to tell you how many cells they visit.

2. It's much easier to write the function and use the function if all branches in an if/else have a consistent return value. If the function sometimes returns the number of visited cells, but sometimes returns None, it will be super inconvenient to use; notice how you had to add int(...) or 0 after every recursive call to fix that issue.

3. The way your matrix is stored as a list of lists, it makes more sense to me to index the rows with y and the columns with x than the other way around.

def _floodfill(matrix, y, x):
    if matrix[y][x] == 9:
        return 0
    else:
        matrix[y][x] = 9
        counter = 1
        if x > 0:
            counter  = _floodfill(matrix, y, x - 1)
        if x < len(matrix) - 1:
            counter  = _floodfill(matrix, y, x   1)
        if y > 0:
            counter  = _floodfill(matrix, y - 1, x)
        if y < len(matrix[0]) - 1:
            counter  = _floodfill(matrix, y   1, x)
        return counter

mat = [
 [9,9,9],
 [9,2,9],
 [9,3,9],
 [9,9,9]
]

c = _floodfill(mat, 1, 1)
print(c)
print(mat)

# 2
# [[9, 9, 9], [9, 9, 9], [9, 9, 9], [9, 9, 9]]

CodePudding user response：

Use a list to save the counter as int are passed by value:

def _floodfill(matrix, x, y, counter):
    if matrix[x][y] != 9:
        matrix[x][y] = 9
        counter[0]  = 1
        # recursively invoke flood fill on all surrounding cells:
        if x > 0:
            _floodfill(matrix, x - 1, y, counter)
        if x < len(matrix) - 1:
            _floodfill(matrix, x   1, y, counter)
        if y > 0:
            _floodfill(matrix, x, y - 1, counter)
        if y < len(matrix[0]) - 1:
            _floodfill(matrix, x, y   1, counter)
        return counter
    else:
        return 0

_floodfill([[9,9,9],
            [9,2,9],
            [9,3,9],
            [9,9,9]], 1, 1, [0])