Злиття континентів
Континентальний дрейф стосується ідеї, що колись континенти Землі були єдиним цілим, а з часом розійшлися і зайняли свої теперішні позиції.
У цій задачі ми розглядаємо зворотний процес — Континентальне злиття.
Для простоти припустимо, що континенти спочатку були об'єднані разом, утворюючи квадрат. З часом квадрат розпався на K різних континентів у формі прямокутників і віддалився від свого джерела.
Вам надано поточні розташування континентів (тобто прямокутників). Ці розташування були окреслені за допомогою супутників. Ваше перше завдання — з'ясувати, чи є надані дані дійсними. Дані є дійсними, якщо ви можете перемістити прямокутники і утворити квадрат. За один хід ви можете взяти будь-який прямокутник і посунути його на одну одиницю в одному з чотирьох напрямків (північ, південь, схід або захід). Континенти можуть ковзати один під одним під час руху — це означає, що більше ніж один континент може займати певну позицію одночасно. Якщо можливо утворити квадрат, то вам також потрібно знайти мінімальну кількість ходів для цього. Кінцеве положення квадрата не є основною турботою тут. Зверніть увагу, що в кінцевому положенні два континенти не можуть перекриватися, а бажаний квадрат не може мати жодних дірок.
Вхідні дані
Перший рядок вхідних даних — це ціле число T (T ≤ 200), яке вказує кількість тестових випадків. Кожен випадок складається з 20 рядків, що містять 20 символів. Кожен символ може бути або точкою (.) що представляє порожній простір, або x (ASCII значення 120). Кожен символ x буде частиною якогось континенту.
Примітки:
У вхідній сітці гарантується, що символи x з різних континентів не будуть суміжними. Будь-який символ x буде частиною якогось прямокутника.
Дві клітини є суміжними, якщо вони мають спільну грань.
У сітці буде рівно 25 символів x.
Кількість континентів, K, буде не більше 5.
Перед початком кожного випадку є порожній рядок.
Прямокутники і бажаний квадрат є паралельними до осей.
Земля тут є плоскою. Тобто, перший і останній рядок НЕ є суміжними один з одним. Те ж саме стосується першого і останнього стовпця.
Вихідні дані
Для кожного випадку спочатку виведіть номер випадку. Якщо неможливо утворити квадрат, переміщуючи прямокутники, виведіть “invalid data”, лапки для ясності. Якщо це можливо, виведіть мінімальну кількість ходів, необхідних для виконання завдання.