Шестиугольные участки
Инженер-строитель, который недавно окончил Чешский технический университет, столкнулся с интересной проблемой и обратился к нам за помощью. Проблема имеет больше экономический, нежели инженерный характер. Инженеру требуется подключить несколько зданий к инфраструктуре. К сожалению, инвестор не является собственником всей земли между этими местами. Таким образом, некоторые владения должны быть куплены в первую очередь.
Земля представляет собой сетку правильных шестиугольных участков земли, каждый из которых является самостоятельной частью и имеет одну и ту же стоимость. Некоторые участки принадлежат инвестору. Они образуют четыре смежные области, каждая из которых содержит одно здание, которое должно быть соединено с другими. Вам следует найти наименьшее количество земельных участков, приобретение которых достаточно для объединения заданных четырех областей.
Вся земля имеет шестиугольную форму, каждая ее часть из шести сторон содержит h участков. На рисунке вверху изображена земля, в которой h = 4. Участки с буквами представляют собой четыре области, которые необходимо объединить между собой. Для приведенного примера достаточно дополнительно приобрести четыре участка. Одно из возможных решений обозначено крестиками.
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест начинается с целого числа h (2 ≤ h ≤ 20) - размера земли. Далее следуют 2h-1 строк, описывающих отдельные "строки" земли (ориентированные всегда как на картинке). Каждый из участков в строках обозначен символом, отличным от пробела. Это значит, что первая строка содержит h символов, вторая h+1 и так далее. Самая длинная строка содержится в середине с 2h-1 символами. Далее "длина" уменьшается, и последняя строка снова содержит h участков.
Участок обозначается точкой (".") для земель, которыми не владеет инвестор, или одной из заглавных букв "A", "B", "C" или "D". Области, в которых находятся одинаковые буквы, всегда связаны друг с другом. То есть между любыми двумя участками одной области всегда существует путь, проходящий по участкам этой области.
Кроме символов, задающих земельные участки, строки могут содержать произвольное количество пробелов в любой позиции для улучшения "читаемости" входных данных. Между двумя буквами (точками) всегда присутствует хотя бы один пробел. За описанием земли следует пустая строка, после чего идет следующий тест. За последним тестом следует строка, содержащая ноль.
Выходные данные
Для каждого теста вывести одну строку - предложение "You have to buy p parcels.", где p - наименьшее количество участков, которое следует приобрести для того чтобы связать все четыре области вместе.
Области считаются связанными, если между ними существует путь только через приобретенные участки.