#algorithm #fill #puzzle #sliding #ice
#алгоритм #заполнить #Головоломка #скольжение #лед
Вопрос:
Моя проблема связана с головоломкой с ледяным слайдом.
Для методов поиска путей BFS — лучший алгоритм, но что, если вы хотите заполнить все пробелы (не камни) в матрице, то есть посетить все ячейки, делая это с наименьшим количеством посещенных ячеек (посещение старых или уже посещенных ячеек считается новым посещением)или наименьшую пройденную ячейку.
Каким может быть возможное решение?
Я думал о некоторых модифицированных BFS. Каждый узел BFS может хранить, сколько ячеек мы посетили, и сколько уникальных ячеек было обнаружено, а также текущее положение.. но это кажется довольно медленным, и я не знаю, когда я должен сообщить программе о завершении (максимум n ^ 2 хода? или idk)
Комментарии:
1. «посещение всех ячеек» … гамильтониан?
2. или один камень на другой камень образует одно ребро с расстоянием в виде веса ребра и пути от начала до конца, как путь Эйлера с минимальным общим весом ребра?
3. Итак, у вас есть двумерный массив, и вы хотите выяснить, какой из элементов является камнем? Почему бы просто не перебрать их? Или вы имеете в виду, что вы выбираете какую-то точку на карте, и она заполняет все ячейки, до которых вы могли бы добраться оттуда, если бы вы могли просто передвигаться и не скользили, пока не уперлись в стену? В этом случае просто используйте этот алгоритм, который использует линии, поэтому он в значительной степени рисует горизонтальную линию от точки, с которой он начался, а затем просто перемещается влево, пока не наткнется на что-то, что не заполнено, а затем записывает, когда ячейка выше или ниже текущей позиции строки не заполнена
4. а затем заполните эти другие строки ниже и выше. Я не совсем понимаю, как называется этот алгоритм, поэтому я не могу его найти. Кроме того, что такого критичного по времени в пошаговой игре, что вы не можете просто использовать floodfill?