I have a question about flood fill algorithms.

I would like to fill a given field that looks like this:

The user should give the starting position

So far I made the below code, but it just fills up and down and I would like it to fill in all 4 directions.

#given field size and markers
number_of_columns = 20
number_of_rows = 10
filled_marker = "x"
empty_marker = " "


def create_grid(number_of_rows, number_of_columns):
    grid = []
    for row in range(number_of_rows):
        grid.append([])
        for column in range(number_of_columns):
            if row == 1 or row == 8 or column == 3 or column == 15:
                grid[row].append(filled_marker)
            else:
                grid[row].append(empty_marker)
    return grid


def print_grid(grid):
    for row in range(number_of_rows):
        for column in range(number_of_columns):
            print(grid[row][column], end="")
        print()


def get_user_input():
    start_row = int(input("Enter the start row: "))
    start_column = int(input("Enter the start column: "))
    return start_row, start_column


def flood_fill(grid, start_row, start_column):
    grid[start_row][start_column] = filled_marker
    print_grid(grid)
    if start_row > 0 and grid[start_row - 1][start_column] == empty_marker:
        flood_fill(grid, start_row - 1, start_column)
    if start_row < number_of_rows - 1 and grid[start_row   1][start_column] == empty_marker:
        flood_fill(grid, start_row   1, start_column)
    if start_column > 0 and grid[start_row][start_column - 1] == empty_marker:
        flood_fill(grid, start_row, start_column - 1)
    if start_column < number_of_columns - 1 and grid[start_row][start_column   1] == empty_marker:
        flood_fill(grid, start_row, start_column   1)


def main():
    grid = create_grid(number_of_rows, number_of_columns)
    start_row, start_column = get_user_input()
    flood_fill(grid, start_row, start_column)


main()

CodePudding user response：

I converted the recursive approach to an iterative approach using a a deque.

You will have to import collections at the start of your script.

def flood_fill(grid, start_row, start_column):
    locations = collections.deque()
    locations.append((start_row, start_column))

    while locations:
        row, column = locations.popleft()
        if grid[row][column] == empty_marker:
            grid[row][column] = filled_marker
            print_grid(grid)
        if row > 0 and grid[row - 1][column] == empty_marker:
            locations.append((row-1, column))
        if row < number_of_rows - 1 and grid[row   1][column] == empty_marker:
            locations.append((row 1, column))
        if column > 0 and grid[row][column - 1] == empty_marker:
            locations.append((row, column-1))
        if column < number_of_columns - 1 and grid[row][column   1] == empty_marker:
            locations.append((row, column 1))

The existing approach checked row - 1 first and then continued to work from there and that means that it now handled row - 1 again from the new location (so a full offset of -2 from the start) and so on.

Now we build a double ended qeue where we take the first element and add the neighbors of this element to the end of the queue if they match the constrictions. Then this task is repeated until the queue is empty.