Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Игра «Flip-Flop»

(Время: 1 сек. Память: 16 Мб Сложность: 54%)
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».

Примеры

INPUT.TXTOUTPUT.TXT
1 wbww
bbww
wwbb
wwbw
2
2 bwbw
wwww
bbwb
bwwb
Impossible

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru