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

1060. Перевертыш

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Для игры «Перевертыш» используется прямоугольное поле 4 × 4 с двусторонними фишками, размещенными на каждом из 16 квадратов поля. Одна сторона каждой фишки – белая, другая – черная, и каждая фишка лежит либо черной, либо белой стороной вверх. Каждый раунд вы переворачиваете несколько фишек, меняя цвет их верхней стороны с черного на белый, и наоборот. Фишки, которые будут переворачиваться, выбираются каждый раунд в соответствии со следующими правилами:
  1. Выберите любую из 16 фишек.
  2. Переверните выбранную фишку, а также все смежные фишки слева, справа, сверху и снизу от выбранной фишки (если они есть).
Problem illustration
Рассмотрим в качестве примера следующее поле:
bwbw
wwww
bbwb
bwwb
Здесь «b» обозначает фишки, лежащие черной стороной вверх, а «w» – фишки, лежащие белой стороной вверх. Если перевернуть первую фишку из третьего ряда (этот выбор показан на рисунке), то поле будет выглядеть так:
bwbw
bwww
wwwb
wwwb
Цель игры состоит в том, чтобы перевернуть все фишки либо белой, либо черной стороной вверх. Напишите программу, которая найдет минимальное количество раундов, необходимых для достижения этой цели.

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

Входные данные состоят из 4 строк с 4 символами «w» или «b», которые обозначают позицию игры.

Результат

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

Примеры

исходные данныерезультат
bwbw
wwww
bbwb
bwwb
Impossible
bwwb
bbwb
bwwb
bwww
4
Источник задачи: 2000-2001 ACM Northeastern European Regional Programming Contest