Дойная корова
Годы до того, как Candy Crush стала невероятно популярной игрой, которая могла бы привести разработчика Saga к многомиллиардному IPO, существовала онлайн-игра под названием Cash Cow, которая до сих пор является частью платформы Webkinz.
Эта однопользовательская игра проходит на доске размером 12 рядов и 10 столбцов, как показано на Рисунке 1. Ряды нумеруются от 1 до 12, начиная с нижнего, а столбцы — от a до j, начиная с левого. Каждая ячейка сетки может содержать либо цветной круг, либо быть пустой. (Мы используем заглавные буквы для обозначения различных цветов, например, B=синий, R=красный и Y=желтый.) На каждом ходу игрок нажимает на круг. Компьютер определяет наибольший "кластер", к которому принадлежит этот круг. Кластер включает начальный круг, а также всех его ближайших горизонтальных и вертикальных соседей с тем же цветом, соседей этих кругов с совпадающими цветами и так далее. Например, если пользователь нажмет на синий круг в ячейке (h10) на Рисунке 1, его кластер будет состоять из ячеек, показанных пустыми кругами на Рисунке 2.
Ход игрока обрабатывается следующим образом. Если указанная ячейка сетки принадлежит кластеру из одного или двух кругов (или если в этой ячейке нет круга), ход теряется. В противном случае, если кластер состоит из 3 или более кругов, все круги в кластере удаляются с доски. Оставшиеся круги затем уплотняются следующим образом:
Круги падают вертикально, заполняя любые пустоты в своем столбце.
Если один или несколько столбцов становятся пустыми, все оставшиеся столбцы сдвигаются влево (каждый непустой столбец остается целым), так что они упаковываются к левой границе доски.
Например, Рисунок 3 показывает доску после удаления кластера из Рисунка 2 после нажатия на (h10).
Как еще один пример, Рисунок 4 ниже изображает обработку последующего нажатия на ячейку (j1). Во время этого хода столбец (e) становится пустым, и оставшиеся столбцы (f) до (j) сдвигаются, чтобы стать столбцами (e) до (i) соответственно. Рисунок 5 предоставляет еще один пример, в котором несколько столбцов уплотняются.
Рисунок 4: Обработка нажатия на ячейку j1.
Рисунок 5: Обработка нажатия на ячейку g2.
Входные данные
Входные данные состоят из нескольких игр, каждая из которых начинается с новой доски. Для каждой игры входные данные начинаются с числа T, обозначающего количество ходов, которые игрок будет делать, с 1 ≤ T ≤ 20. Далее следует начальная конфигурация доски, которая всегда имеет 12 рядов и 10 столбцов в каждом ряду, с заглавными буквами, обозначающими различные цвета. В начальной доске никогда не будет пустых ячеек. После представления начальной доски будет T дополнительных строк входных данных, каждая из которых обозначает ячейку сетки; мы полагаемся на систему координат, иллюстрированную на вышеуказанных рисунках, с маленькой буквой от a до j, обозначающей столбец, и числом от 1 до 12, обозначающим ряд. Мы отмечаем, что если игрок нажимает на ячейку сетки, в которой в данный момент нет круга, этот ход просто теряется.
Конец всего ввода будет обозначен строкой с числом 0.
Выходные данные
Для каждой игры выведите одну строку, обозначающую количество кругов, оставшихся на доске после обработки всех ходов игрока.