printОбластная олимпиада школьников по информатике (личное первенство)

print5. Зельеделие (25 баллов)

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Рон смешал несколько ингредиентов зелья в пробирке и стал наблюдать за выпадающим осадком.
Напишите программу, которая рассчитает форму осадка. Расчёт выполняется для двумерного варианта задачи на поле из клеток. Все ингредиенты падают вниз синхронно с одинаковой скоростью. Группа ингредиентов движется вниз в случае, если движению ничего не мешает (т.е. под ней только пустые клетки). Если в соседних клетках, имеющих общую сторону, будут находиться одинаковые ингредиенты, то они становятся химически связанными и могут двигаться далее вниз только вместе.
В первой строке входного файла содержатся два целых числа, разделенных пробелом – размеры пробирки `N` (`1\ ≤\ N\ ≤\ 100`) и `M` (`1\ ≤\ M\ ≤\ 100`). Далее следует `N` строк, содержащих по `M` символов – начальное состояние. Символ '.' (точка) означает пустую клетку (раствор). Различные ингредиенты зелья обозначены различными латинскими буквами (прописными или строчными, регистр букв важен) и цифрами.
В первой строке выходного файла вывести `N` строк, содержащих по `M` символов – получившийся осадок.

Пример ввода

4 5
aBBB.
.aBcc
.BB..
.....

Вывод для примера

.....
.BBB.
aaB..
.BBcc
loading