Шестикутні ділянки
Інженер-будівельник, який нещодавно закінчив Чешський технічний університет, зіткнувся з цікавою проблемою і звернувся до нас за допомогою. Проблема має більше економічний, ніж інженерний характер. Інженеру потрібно підключити декілька будівель до інфраструктури. На жаль, інвестор не є власником усієї землі між цими місцями. Таким чином, деякі ділянки повинні бути куплені у першу чергу.
Земля являє собою сітку правильних шестикутних ділянок землі, кожна з яких є самостійною частиною і має одну і ту ж вартість. Деякі ділянки належать інвестору. Вони утворюють чотири суміжні області, кожна з яких містить одну будівлю, яка должна бути з'єднана з іншими. Вам потрібно знайти найменшу кількість земельних ділянок, придбання яких достатньо для об'єднання заданих чотирьох областей.
Уся земля має шестикутну форму, кожна її частина з шести сторін містить 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 - найменша кількість ділянок, які потрібно придбати для того, щоб зв'язати усі чотири області разом.
Області вважаються зв'язними, якщо між ними існує шлях лише через придбані ділянки.