Объединение Континентов
Континентальный дрейф — это идея о том, что когда-то континенты Земли составляли единое целое, а затем разошлись, заняв свои нынешние позиции.
В этой задаче нас интересует обратный процесс — Континентальное слияние.
Для простоты предположим, что изначально континенты были объединены в квадрат. Со временем этот квадрат распался на K различных континентов в форме прямоугольников и удалился от своего исходного положения.
Вам даны текущие местоположения континентов (то есть прямоугольников), определенные с помощью спутников. Ваша первая задача — выяснить, являются ли предоставленные данные допустимыми. Данные считаются допустимыми, если можно перемещать прямоугольники, чтобы образовать квадрат. За один ход вы можете сдвинуть любой прямоугольник на одну единицу в одном из четырех направлений (север, юг, восток или запад). Континенты могут скользить друг под другом во время движения, то есть более одного континента могут находиться в одной и той же позиции одновременно. Если возможно образовать квадрат, вам также нужно определить минимальное количество ходов для этого. Конечное положение квадрата не имеет значения. Обратите внимание, что в конечном положении два континента не могут перекрываться, и желаемый квадрат не должен иметь дыр.
Входные данные
Первая строка ввода — это целое число T (T ≤ 200), обозначающее количество тестов. Каждый тест состоит из 20 строк, содержащих 20 символов. Каждый символ может быть либо точкой (.) для обозначения пустого пространства, либо x (ASCII значение 120). Каждый символ x будет частью какого-то континента.
Примечания:
В входной сетке гарантируется, что символы x из разных континентов не будут смежными. Любой символ x будет частью какого-то прямоугольника.
Две ячейки считаются смежными, если они имеют общую грань.
В сетке будет ровно 25 символов x.
Количество континентов, K, будет не более 5.
Перед началом каждого теста будет пустая строка.
Прямоугольники и желаемый квадрат параллельны осям.
Земля здесь плоская. То есть, первая и последняя строка НЕ являются смежными друг с другом. То же самое относится к первому и последнему столбцу.
Выходные данные
Для каждого теста сначала выведите номер теста. Если невозможно образовать квадрат, перемещая прямоугольники, выведите "invalid data" (в кавычках для ясности). Если это возможно, выведите минимальное количество ходов, необходимых для выполнения задачи.