eolymp
bolt
Try our new interface for solving problems
Məsələlər

Прыжки с трамплина

Прыжки с трамплина

\includegraphics{https://static.e-olymp.com/content/ac/ac8850a3a982c2fd95eef3ea11e9e30398ee5bca.jpg} Прыгуны на лыжах с трамплина -- люди с особой психологией. Чтобы совершать \textbf{200}-метровые полеты, необходима железная воля и четкий психологический настрой. Каждый из них имеет свой рецепт настроя перед прыжком. Кто-то слушает любимую музыку, кто-то пытается в сотый раз прокрутить в уме момент будущего полета. А некоторые играют в популярную игру <<\textbf{Bubble breaker}>>. Игровое поле разделено на клетки, в каждой из которых расположен шарик одного из четырех цветов -- синего, красного, зеленого или желтого. За одни ход игрок должен удалить любую область из двух или более смежных шариков одного цвета. Клетки области являются смежными, если имеют общую сторону. За каждый ход игрок получает количество очков, равное \textbf{P*(P-1)}, где \textbf{P} -- количество шариков в удаленной области. Набранные очки суммируются. После удаления шарики, находящиеся выше удаленной области, падают вертикально вниз, заполняя пустоты. Понятно, что падение шарика происходит до тех пор, пока он не упрется в занятую клетку. Игра заканчивается, когда не осталось областей, пригодных для удаления. Один из прыгунов придумал усовершенствованную жадную стратегию для этой игры. Для каждого хода применимы следующие соображения: \begin{itemize} \item Если существует такой ход, который приведет к образованию выгодной ситуации для следующего хода, выполнить этот и следующий ход. Такой ход назовем ходом первого типа. \item Если такого хода не существует, выполнить оптимальный ход. Такой ход назовем ходом второго типа. \end{itemize} Ход на шаге \textbf{k} приводит к образованию выгодной ситуации для хода на шаге \textbf{k+1}, если ходом на шаге \textbf{k+1} можно будет набрать больше очков, чем любым другим ходом на шаге \textbf{k}. Ход на шаге \textbf{k} называется оптимальным, если он приносит большее число очков, чем любой другой ход на шаге \textbf{k}. Если существует несколько подходящих ходов второго типа, кандидатом на удаление является область, которая находится левее на игровом поле. Если же и в этом случае существует несколько оптимальных ходов, необходимо удалить область, которая находится выше на игровом поле. Положение области определяется положением самой верхней клетки из самых левых клеток этой области. Понятно, что, если существует несколько ходов первого типа, следует выбрать такой ход, который принесет максимальное количество очков на следующем ходе. Если все еще существует несколько таких ходов, выбрать из них оптимальный (в случае возможного равенства оптимальных ходов следует руководствоваться приведенным выше правилом о выборе области в зависимости от положения на игровом поле). Спортсмены не хотят надолго отвлекаться от соревнования, поэтому требуют от вас определить количество очков, которое можно набрать, руководствуясь этой стратегией. \InputFile В первой строке записаны через пробел числа \textbf{N} и \textbf{M} (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{50}) -- размеры игрового поля. Далее записано игровое поле -- \textbf{N} строк по \textbf{M} символов из множества \{ \textbf{Y}, \textbf{B}, \textbf{R}, \textbf{G} \}. Символ означает цвет шарика: \textbf{Y} (\textbf{yellow}) -- желтый, \textbf{B} (\textbf{blue}) -- синий, \textbf{R} (\textbf{red}) -- красный, \textbf{G} (\textbf{green}) -- зеленый. \OutputFile Необходимо вывести единственное число -- количество очков.
Zaman məhdudiyyəti 15 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
5 7
GGGBBRB
GGYRRYY
BYYGGGY
BRBBRRR
RBRRYYB
Çıxış verilənləri #1
132
Müəllif Бирюков С.В.
Mənbə IV Открытая олимпиада ЮФУ