Игра «Flip-Flop»

В игре «Flip-Flop» используется прямоугольное поле 4×4 с двухсторонними фишками, расположенными на каждом из 16 квадратов. Одна сторона каждой фишки имеет черный цвет, а другая – белый. При каждом ходе происходит выбор клетки, рядом с которой (слева, справа, сверху, снизу и в центре) происходит инверсия от 3х до 5ти фишек таким образом, что они меняют свой цвет на противоположный.

Рассмотрим в качестве примера следующую позицию:

   bwbw
   wwww
   bbwb
   bwwb

Здесь «b» обозначает черный цвет лицевой стороны фишки, а «w» - белый. Если мы в качестве хода выбираем поле, расположенное в 3й строке и 1м столбце, то результат будет следующим:

   bwbw
   bwww
   wwwb
   wwwb

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

Входные данные

Входной файл INPUT.TXT содержит 4 строки по 4 символа «w» или «b» в каждой, описывающие цвета фишек.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число – минимальное количество ходов, необходимых для достижения цели. Если исходная доска уже имеет набор фишек одинакового цвета, то следует вывести 0. Если решения не существует, то следует вывести слово «Impossible».

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]