Кто хочет поломать немного мозг?

Question

[Atllantis]

Мой мозг уже выкипает... И я никак не могу придумать алгоритм для слудующего:
И так, есть координатная сетка с ячейками/пикселями/квадратами и т.п. (придумай ещё!):

Нужно все квадраты (красные) разместить друг на друге внизу.
Всё вроде бы просто, но есть одно НО. Есть спаяные квадраты, часть которых не может быть ниже или выше другой.
Например:
Квадраты в ячейках [5,2] и [5,3] опустятся на 1 ячейку вниз по оси Y.
Тогда спаяный квадрат должен будет опуститься только на две ячейки вниз.

В итоге должно получиться так:

Если бы не было спаяных квадратов, то решение было бы простым:
Проходим циклом по оси X, и в каждой клетке (по оси Х) проверяем все ячейки по оси У (снизу вверх). Считаем кол-во пустых клеток до квадрата и опускаем квадрат вниз на подсчитанное кол-во пустых клеток.
Но как быть со спаянными квадратами?

Comments

[Mercury13]

По каким правилам они спаиваются?

Answer 1

[tsarevfs]

Первым делом выделяем связанные фигуры.
Изначально каждый отдельный квадрат и каждую фигуру помечаем "свободным".
В цикле, пока есть свободные квадраты:
пробегаемся по всем квадратам, если под квадратом пол или "замороженный" квадрат, морозим его;
пробегаемся по свободным фигурам, если в фигуре появились замороженные квадраты, морозим фигуру и остальные квадраты в фигуре;
пробегаемся по свободным фигурам, каждый квадрат из нее опускаем на 1 клетку вниз;
идем в начало цикла.

Если поле очень большое, можно попытаться посчитать более эффективно. Но это нужно заморочиться. Идея в том, что можно, пробежавшись по столбцам, оценить насколько могут фигуры двигаться относительно друг друга. И потом посмотреть на сколько их можно все опустить. Но дальше хз что делать =)

Answer 2

[mamkaololosha]

010
010
010
Это палка. Остальные фигуры можешь сделать так же. И колизить единицы.

Comments

[Atllantis]

Можно немного поподробнее? Пример, например. :)

Answer 3

[Антон Перевощиков]

Проходим циклом по оси X, и в каждой клетке (по оси Х) проверяем все ячейки по оси У (снизу вверх). Считаем кол-во пустых клеток до квадрата и опускаем квадрат вниз на подсчитанное кол-во пустых клеток.

Зачем вы опускаете столбцы? Опускайте строки, проходите циклом снизу вверх и итерируйте до тех пор, пока будут изменения.

Comments

[Atllantis]

Да, так и думал, но дело в том, что квадраты могут быть спаяны как по горизонтали, так и по вертикали одновременно и с большим кол-вом квадратов. Например что-то на подобии такого:
┌─┐ ┌─┐
└─┘ └─┘
┌─┐┌─┐┌─┐┌─┐
└─┘└─┘└─┘└─┘
┌─┐
└─┘

[Spaceoddity]

Ну идёте снизу вверх, наткнулись на квадрат, запускает метод "опускания блока":
1) если у квадрата есть "прилипший сосед", смотрим есть ли пустое место под квадратом.
1а) места нет, выходим из метода (можно сразу пометить координаты этого блока как непригодные для опускания и не проверять их)
1б) место есть, проверяем наличие места внизу для "прилипшего соседа" и т.д.
1в) место есть для всех "прилипших соседов" - смещаем их всех вниз на одну клетку и запускаем метод ещё раз.
2) "прилипшего соседа" нет - запускаем упрощенный метод опускание блока (проверяет наличие пустого места только под актуальным квадратом и опускает его пока есть возможность).
3) PROFIT!
P.S. Это тестовое задание что ли?

[Spaceoddity]

Spaceoddity: Добавлю что в проверку на наличие свободного места внизу не должны входить "прилипшие соседи" этого же блока. Т.е. если при проверке, показывает что внизу не пустая ячейка, а "прилипший сосед" - считаем что место есть.
У вас в этом моменте сложность была?))

[Ocelot]

Spaceoddity: там не всё так просто. Представьте себе две фигуры в виде [ и ], сцепленные друг с другом. Они так и будут висеть, опираясь друг на друга, а должны упасть как единое целое.

[Spaceoddity]

Ocelot: ну тогда просто добавим условие - будем считать что если один блок как-то опирается на другой - то это один общий блок))

Answer 4

[xmoonlight]

Это обычный тетрис в невесомости.
Вначале поднимаем все фигуры вверх и заполняем строку за строкой.
Если надо лучше - уже комбинаторика.

Answer 5

[abcd0x00]

Проходим циклом по оси X, и в каждой клетке (по оси Х) проверяем все ячейки по оси У (снизу вверх).

Представь себе спаянную фигуру в виде лестницы из квадратов. При этом она спаяна целиком. И как ты её будешь проверять?

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