Python 洪水填充算法北、南、东、西

Question

我有一个关于洪水填充算法的问题。

我想填写如下所示的给定字段：

用户应给出起始位置

到目前为止，我制作了以下代码，但它只是向上和向下填充，我希望它能填充所有 4 个方向。

#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()

Answer 1

我使用 deque.

将递归方法转换为迭代方法

您必须 import collections 在脚本的开头。

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))

现有方法首先检查 row - 1，然后从那里继续工作，这意味着它现在从新位置再次处理 row - 1（因此从一开始就有 -2 的完整偏移量) 等等。

现在我们构建一个双端队列，我们在其中获取第一个元素，并将该元素的邻居添加到队列的末尾（如果它们匹配限制条件）。然后重复这个任务，直到队列为空。

Python 洪水填充算法北、南、东、西

Python flood fill algorithm north, south, east, west

python

algorithm

flood-fill