Злиття континентів#3101
Континентальний дрейф — це ідея про те, що колись континенти Землі були з'єднані воєдино, а з часом вони віддалились один від одного й опинилися на нинішніх місцях.
У цій задачі ми розглядаємо зворотний процес — континентальне злиття.
Задля спрощення припустимо, що спочатку континенти були з'єднані разом, утворюючи квадрат. Згодом цей квадрат розпався на різних континентів у формі прямокутників і відплив на нові позиції.
Вам дано теперішнє розташування континентів (тобто прямокутників). Такі місцезнаходження були визначені за допомогою супутників. Ваше перше завдання — визначити, чи коректні надані дані. Дані вважаються коректними, якщо ви можете пересунути прямокутники, щоб утворити квадрат. За один хід ви можете вибрати будь-який прямокутник і пересунути його на одну клітинку в одному з чотирьох напрямків (північ, південь, схід або захід). Під час переміщення континенти можуть проходити один під одним — тобто більше одного континенту можуть займати одне й те саме місце у процесі руху. Якщо можливо скласти квадрат, вам також потрібно знайти мінімальну кількість ходів, необхідних для цього. Положення кінцевого квадрата не має значення. Зауважте, що у фінальному положенні жодні два континенти не можуть перекриватися, а утворений квадрат не повинен містити порожніх клітин.
Перший рядок містить ціле число (T \leq 200) — кількість тестових випадків. Кожен випадок складається з рядків, кожен з яких містить символів. Кожен символ — або крапка (.), що позначає порожню клітинку, або (ASCII-код ). Кожен є частиною деякого континенту.
Примітки:
У вхідній сітці символи з різних континентів не суміжні. Кожен належить лише одному прямокутнику.
Дві клітинки вважаються суміжними, якщо вони мають спільну сторону.
У сітці рівно символів .
Кількість континентів не перевищує .
Перед кожним тестовим випадком є порожній рядок.
Прямокутники й цільовий квадрат орієнтовані вздовж осей.
Земля тут плоска. Тобто перший і останній рядок не суміжні. Те ж саме стосується першого й останнього стовпчика.
Для кожного випадку виведіть номер тесту. Якщо неможливо скласти квадрат пересуванням прямокутників, виведіть "invalid data" (із лапками для ясності). Якщо це можливо, виведіть мінімальну кількість необхідних ходів.
Приклад 1