ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2009, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Another Ball Killer

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Участники часто задаются вопросом, чем же занимаются члены жюри во время соревнования. Некоторые думают, что они судорожно правят тесты. Другие говорят, что они с азартом следят за ходом соревнования и даже делают ставки на победителей. Но на самом деле члены жюри предпочитают в это время играть в компьютерные игры, отдав слежение за контестом на откуп бездушным программам.
Одна из любимых игр жюри — Another Ball Killer. Её правила очень просты:
  1. Игра ведётся одним человеком на прямоугольном поле размера n × m. В начальный момент в каждой ячейке поля находится шарик одного из пяти цветов: синего, зелёного, красного, белого или жёлтого.
  2. На каждом ходу игрок выбирает некоторую фигуру (связную группу из двух или более шариков одного цвета; связность определяется по общей стороне) и удаляет её с поля. После этого шарики, лежащие над удалёнными, падают вниз. Если образуется колонка без шариков, то все колонки, стоящие справа от неё, сдвигаются влево.
    На рисунке ниже показано, как изменится поле после удаления самой большой фигуры:
    За свой ход игрок получает k × (k − 1) очков, где k — размер удалённой фигуры, то есть количество шариков в ней.
  3. Игра заканчивается, когда на поле не остаётся ни одной фигуры. Цель игры — набрать к её концу как можно больше очков.
Problem illustration
Ленивые члены жюри играют в Another Ball Killer по следующему алгоритму:
01  Выбрать цвет одного из шариков на поле в качестве основного
02  Пока на поле есть хотя бы одна фигура:
03      Пока на поле есть хотя бы одна фигура неосновного цвета:
04          Удалить самую большую фигуру неосновного цвета
05      Если на поле есть фигура основного цвета:
06          Удалить самую большую фигуру основного цвета
В случае неоднозначностей в строках 04 и 06 следует выбирать ту из наибольших фигур, в которую входит самый нижний шарик (а если таковых несколько, то самый левый из них).
А председатель жюри настолько ленив, что даже не думает, какой цвет выбрать основным. Одной клавишей он запускает заранее написанную программу, которая перебирает все цвета, представленные на поле, и для каждого подсчитывает количество очков, которое можно набрать, выбрав этот цвет в качестве основного. Попробуйте и вы написать такую программу.

Исходные данные

Первая строка содержит размеры поля n и m (1 ≤ n, m ≤ 50). В каждой из следующих n строк записано по m букв, обозначающих цвет шарика в соответствующей ячейке поля (B — синий, G — зелёный, R — красный, W — белый, Y — жёлтый). Строки игрового поля задаются в порядке от верхней к нижней.

Результат

Выведите по одной строке для каждого цвета, представленного на поле: сперва выведите букву, обозначающую цвет, затем двоеточие, пробел и количество очков, которое заработает председатель жюри, если выберет этот цвет в качестве основного. Цвета должны быть рассмотрены в следующем порядке: синий, зелёный, красный, белый, жёлтый.

Пример

исходные данныерезультат
3 6
WWWGBG
WBGGGB
GGGGBB
B: 74
G: 92
W: 74
Автор задачи: фольклор (подготовка — Евгений Крохалев)
Источник задачи: NEERC 2009, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1715. Another Ball Killer