eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Стрибки з трампліну

Стрибки з трампліну

\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 Необхідно вивести єдине число -- кількість очок.
Ліміт часу 15 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
5 7
GGGBBRB
GGYRRYY
BYYGGGY
BRBBRRR
RBRRYYB
Вихідні дані #1
132
Автор Бірюков С.В.
Джерело IV Відкрита олімпіада ЮФУ