Алгоритм заливки Python на север, юг, восток, запад

У меня вопрос по поводу алгоритмов заливки.

Я хотел бы заполнить данное поле, которое выглядит так:

Field

Пользователь должен указать начальную позицию

Пока я сделал приведенный ниже код, но он просто заполняется вверх и вниз, и я хотел бы, чтобы он заполнял все 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()

Это из-за вашего рекурсивного подхода. Я бы использовал здесь очередь FIFO.

Matthias 22.04.2022 23:11

Можете ли вы предоставить полный код и входные данные, необходимые для воспроизведения ваших наблюдаемых результатов? А также ожидаемый результат и наблюдаемые результаты?

kcsquared 22.04.2022 23:15

@kcsquared Для меня код и описание были довольно понятными. Я согласен, что было бы удобнее, если бы код примера определял фиксированные значения. Но просто введите значение 6 для начальной строки и начального столбца, и вы увидите, что произойдет.

Matthias 22.04.2022 23:51

@Matthias Я согласен, что код и описание были очень понятными. Однако, когда я ввел 6 для начальной строки и столбца, кажется, что все работает, как и ожидалось, для заливки заливкой - центральная область полностью заполнена. Вы видите что-то другое? Я не могу воспроизвести ошибочный вывод.

kcsquared 23.04.2022 00:00

Да в итоге все заполнено. Это больше о том, как это происходит. В процессе каждый шаг заполнения сетки распечатывается, чтобы вы могли видеть различные состояния. Вы можете видеть, что он предпочитает вертикали (из-за алгоритма), переключая столбец только после его полного заполнения. И вопрос примерно такой: «Как мне сделать так, чтобы это выглядело более естественно, расширяясь во все стороны».

Matthias 23.04.2022 00:10

@Matthias Я думаю, это возможно; если так, то формулировка крайне запутанная. Я всегда интерпретировал it just fills up and down and I would like it to fill in all 4 directions как означающий, что он заполняется только вверх и вниз, а не влево и вправо.

kcsquared 23.04.2022 00:18

Эй, извините, если я не ясно выразился. Я все еще новичок в кодировании в целом, и английский не мой первый язык. Я также только начал python две недели назад. В будущем я постараюсь сделать свои вопросы/сообщения более понятными! :) Но пока @Matthias помог мне со своей версией. Я буду больше исследовать его код! :D Спасибо всем.

Sergej 23.04.2022 14:46
3 метода стилизации элементов HTML
3 метода стилизации элементов HTML
Когда дело доходит до применения какого-либо стиля к нашему HTML, существует три подхода: встроенный, внутренний и внешний. Предпочтительным обычно...
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
0
7
50
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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 от начала) и так далее.

Теперь мы создаем двустороннюю очередь, в которой мы берем первый элемент и добавляем соседей этого элемента в конец очереди, если они соответствуют ограничениям. Затем эта задача повторяется до тех пор, пока очередь не станет пустой.

Другие вопросы по теме