我有一個關于洪水填充演算法的問題。
我想填寫如下所示的給定欄位：
用戶應給出起始位置
到目前為止，我制作了以下代碼，但它只是向上和向下填充，我希望它填充所有 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()
uj5u.com熱心網友回復：
我使用 aa 將遞回方法轉換為迭代方法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）等等。
現在我們構建一個雙端佇列，我們??在其中獲取第一個元素并將該元素的鄰居添加到佇列的末尾，如果它們與收縮匹配。然后重復此任務，直到佇列為空。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/463763.html
上一篇：按特定順序對陣列進行排序
下一篇：這個偽代碼的復雜度（?）是多少？