Алгоритм падения элементов сетки

Ответ 1

Идея

Определить набор замороженных объектов индуктивно следующим образом:

• Объект, касающийся дна, заморожен.

• Объект, лежащий на замороженном объекте, заморожен.

Интуитивно, именно замороженные объекты достигли своего последнего места. Вызовите незамороженные объекты активными.

Претензия. Все активные объекты могут одновременно упасть на единицу вниз.

Доказательство. Конечно, активный объект не ударит по другому активному объекту, так как их относительное положение относительно друг друга не изменяется. Активный объект также не ударит по замороженному объекту. Если это так, то активный объект был фактически заморожен, потому что он лежал на замороженном объекте. Это противоречит нашему предположению.

Наш алгоритм очень высокого псевдокода будет выглядеть следующим образом:

while (there are active objects):
    move active objects downwards simultaneously until one of them hits a frozen object
    update the status (active/frozen) of each object

Обратите внимание, что по крайней мере один объект становится замороженным в каждой итерации цикла while. Кроме того, каждый объект становится замороженным ровно один раз. Эти наблюдения будут использоваться при анализе сложности времени выполнения фактического алгоритма.

Алгоритм

Мы используем концепцию времени для повышения эффективности большинства операций. Время измеряется начиная с 0, и каждое движение элемента активных объектов занимает 1 единицу времени. Заметим, что когда мы находимся в момент времени t, смещение всех объектов, активных в данный момент времени t, в точности равно t единиц вниз.

Обратите внимание, что в каждом столбце относительный порядок каждой ячейки фиксирован. Одним из следствий этого является то, что каждая ячейка может сразу останавливаться в большинстве других клеток от падения. Это наблюдение можно было бы использовать для эффективного прогнозирования времени следующего столкновения. Мы также можем избежать "обработки" каждой ячейки не более одного раза.

Мы индексируем столбцы, начиная с 1 и увеличивая слева направо; и строки с высотой, начиная с 1. Для простоты внедрения введем новый объект под названием bottom - который является единственным объектом, который изначально заморожен, и состоит из всех ячеек на высоте 0.

Структуры данных Для эффективной реализации мы сохраняем следующие структуры данных:

• Ассоциативный массив A, содержащий конечное смещение каждой ячейки. Если ячейка активна, ее запись должна быть, скажем, -1.

• Для каждого столбца k мы сохраняем набор S_k начальных номеров строк активных ячеек в столбце k. Нам нужно иметь возможность поддерживать последующие запросы и удаления на этом наборе. Мы могли бы использовать дерево Van Emde Boas и отвечать на каждый запрос в O(log log H); где H - высота сетки. Или мы могли бы использовать сбалансированное двоичное дерево поиска, которое может выполнять эти операции в O(log N); где N - число ячеек в столбце k.

• Очередь приоритетов Q, которая будет хранить активные ячейки с ее ключом как ожидаемое время его будущего столкновения. Опять же, мы могли бы пойти либо для дерева vEB для времени запроса O(log log H), либо для очереди с приоритетом O(log N) для каждой операции.

Реализация

Ниже приводится подробный псевдокод алгоритма:

Populate the S_k with active cells
Initialize Q to be an empty priority queue

For every cell b in bottom:
    Push Q[b] = 0

while (Q is not empty):
    (x,t) = Q.extract_min()     // the active cell x collides at time t
    Object O = parent_object(x)
    For every cell y in O:
        A[y] = t                // freeze cell y at displacement t
        k = column(y)           
        S_k.delete(y)
        a = S_k.successor(y)    // find the only active cell that can collide with y
        if(a != nil):
            // find the expected time of the collision between a and y
            // note that both their positions are currently t + (their original height) 
            coll_t = t + height(a) - height(y) - 1
            Push/update Q[a] = coll_t

Окончательная позиция любого объекта может быть получена путем запроса A для перемещения любой ячейки, принадлежащей этому объекту.

Время выполнения

Мы обрабатываем и замерзаем каждую ячейку ровно один раз. Мы выполняем постоянное количество поисков при замораживании каждой ячейки. Мы предполагаем, что поиск parent_object может выполняться в постоянное время. Сложность всего алгоритма O(N log N) или O(N log log H) в зависимости от используемых структур данных. Здесь N - общее количество ячеек по всем объектам.

Ответ 2

И теперь что-то совершенно другое:)

Каждая часть, которая лежит на земле, фиксирована. Фиксируется каждая часть, которая опирается на фиксированную деталь. Остальное может двигаться. Переместите незафиксированные куски на 1 квадрат вниз, повторите, пока ничего не изменится.

Ответ 3

Я не очистил все детали, но я думаю, что следующее выглядит несколько систематическим:

• Рассматривая всю картину как график, вам нужен топологический вид всех вершин, т.е. элементов. Элемент A должен быть до элемента B при сортировке, если какая-либо часть A находится ниже любой части B. Тогда, когда у вас есть отсортированные по топологии элементы, вы можете просто перебирать их в этом порядке и определять позиции - поскольку все элементы ниже текущего уже есть фиксированные позиции.
• Чтобы иметь возможность выполнять топологическую сортировку, вам нужен ациклический граф. Затем вы можете использовать некоторые алгоритмы для Сильно подключенные компоненты, чтобы найти все циклы и сжать их в одиночные вершины. Затем вы можете выполнить верхнюю сортировку на полученном графике.
• Чтобы найти позиции частей в SCC: сначала рассмотрите его как одну большую часть и определите, где она закончится. Это определит некоторые фиксированные части, которые больше не могут двигаться. Удалите их и повторите ту же процедуру для остальных частей этого SCC (если есть), чтобы узнать их конечные позиции.

Третья часть - единственная, которая кажется вычислительной интенсивностью - если у вас очень сложная структура для фигур, но она должна быть более оптимальной, чем попытка перемещать фигуры на один квадрат сетки за раз.

Ответ 4

Хорошо, так что это выглядит следующим образом -

• переходим к шагу
• на каждом шаге мы строим ориентированный граф, вершины которого представляют собой набор объектов, а ребра следующие: = >

1), если x и y - два объекта, тогда добавьте ребро x- > y, если x не может двигаться до тех пор, пока не будет перемещен y. Заметим, что мы можем иметь как x- > y, так и y- > x ребра.

2), кроме того, есть объекты, которые больше не могут перемещаться, так как они находятся внизу, поэтому мы раскрашиваем их вершины как синие. Остальные вершины являются красными.

2) в ориентированном графе мы находим все сильно связанные компоненты с использованием алгоритма Косараджу/алгоритма Тарьяна и т.д. (В случае, если вы не знакомы с SCC, они являются чрезвычайно мощной техникой, и вы можете обратиться к алгоритму Косараджу.) Как только мы получаем SCC, мы сокращаем их до небольшой вершины, то есть мы заменяем SCC на одну вершину, сохраняя все внешние (до SCC) ребра. Теперь, если какая-либо из вершин в SCC синей, мы окрасим новую вершину как синюю, иначе она красная. Это означает, что если один объект не может перемещаться в SCC, то никто не может.

3) граф, который вы получите, будет ориентированным ациклическим графом, и вы можете сделать топологический вид. Пройдите по вершине в порядке возрастания верхней нумерации и пока вы увидите вершину красного цвета и переместите объекты, представленные вершиной.

продолжайте этот шаг, пока вы не сможете больше переместить какую-либо вершину на шаге 3.

Если два объекта A и B перекрываются, мы говорим, что они несовместимы друг с другом. Для доказательства корректности докажем следующие леммы 1) "если я перемещаю SCC, то ни один из объектов в нем не вызывает несогласованности между собой". 2) "когда я перемещаю объект на шаге 3, тогда я не выношу несоответствий"

Теперь вам предстоит формально доказать правильность и найти подходящие структуры данных для ее эффективного решения. Дайте мне знать, если вам нужна помощь.

Ответ 5

EDITED несколько раз. Я думаю, что это все, что вам нужно сделать:

• Найдите все фигуры, которые могут падать независимо друг от друга и объединить их в эквивалентную большую фигуру (например, T и назад C на вашем снимке.)

• Итерации через все части, перемещая их на максимальное направление вниз, прежде чем они что-то ударят. Повторяйте, пока ничего не двигается.