Поле для игры "Перевёртыши" представляет собой
прямоугольную доску, расчерченную на N ´ M
квадратов. На каждом квадрате есть кнопка и лампочка. Лампочка может светиться
одним из трёх цветов: красным, зелёным или синим. При нажатии на кнопку,
расположенную на какой-либо клетке, меняется цвет лампочки в этой клетке и во
всех клетках, имеющих с ней общую сторону. Смена цвета лампочек всегда
осуществляется по правилу: красный меняется на зелёный, зелёный на синий, а
синий на красный. Цель игры — добиться того, чтобы лампочки на всём поле
засветились одним цветом.
Требуется написать программу, которая находит
минимальное количество нажатий кнопок для того, чтобы достигнуть цели игры.
Формат входных данных:
В первой строке входного файла содержатся разделённые
пробелом натуральные числа N и M (1 £ N, M £ 8), где N — количество
строк доски, а M — количество столбцов. Далее в N строках содержится по M символов, задающих цвета лампочек клеток поля. Символ
"R" означает
красный цвет, "G"
— зелёный, а "B" —
синий.
Формат выходных данных:
Выходной файл должен содержать единственное целое число —
наименьшее количество нажатий кнопок, необходимое для того, чтобы лампочки на
всём поле засветились одним цветом. Входные данные будут таковы, что это всегда
можно будет сделать.
Примеры файлов входных и выходных данных.
|
INPUT
|
OUTPUT
|
|
5 5
BBBGG
BBBBG
BBBBB
GBBBB
GGBBB
|
2
|
|
1 3
RBB
|
1
|
