대륙의 합체

시간 제한1초메모리 제한128 MB

요약

20x20 격자에 놓인 넓이 합 25인 K개의 직사각형을 평행이동해 정사각형을 채울 수 있는지 판정하고, 필요한 최소 이동 횟수를 구한다.

난이도: 어려움10점 중 10점
유형: 완전 탐색, 수학, 기하, 구현
정답자: 아직 제출이 없습니다

문제

대륙 이동설은 지구의 대륙들이 한때 하나의 커다란 땅덩어리로 붙어 있었고, 오랜 시간에 걸쳐 서로 갈라져 지금의 위치에 이르렀다는 학설입니다.

이 문제에서는 그 반대 과정, 즉 대륙이 다시 합쳐지는 과정을 다룹니다.

대륙들이 원래는 하나의 커다란 정사각형으로 붙어 있었다고 가정합니다. 시간이 지나면서 이 정사각형은 $K$ 개의 직사각형 대륙으로 쪼개져 원래 자리에서 멀어졌습니다.

위성으로 윤곽을 측정한 대륙(직사각형)들의 현재 위치가 주어집니다. 먼저 해야 할 일은 이 데이터가 유효한지 판정하는 것입니다. 직사각형들을 움직여 하나의 정사각형을 만들 수 있으면 데이터는 유효합니다. 한 번의 이동에서는 직사각형 하나를 골라 동·서·남·북 네 방향 중 한 방향으로 1칸 밀 수 있습니다. 이동하는 동안에는 대륙들이 서로의 아래로 미끄러져 들어갈 수 있어, 같은 위치를 여러 대륙이 동시에 차지해도 됩니다. 정사각형을 만들 수 있다면, 그렇게 하는 데 필요한 최소 이동 횟수도 구해야 합니다. 완성된 정사각형이 최종적으로 어디에 놓이는지는 중요하지 않습니다. 단, 최종 배치에서 두 대륙이 겹쳐서는 안 되며, 정사각형은 구멍 없이 빈틈없이 채워져야 합니다.

입력

첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$ ( $T \le 200$ )가 주어집니다. 각 테스트 케이스는 20글자로 이루어진 20줄로 구성됩니다. 각 글자는 빈 칸을 나타내는 점(.)이거나 x(ASCII 120)입니다. 모든 x는 어떤 대륙에 속합니다.

참고:

서로 다른 대륙에 속한 x끼리는 인접하지 않습니다. 모든 x는 어떤 직사각형의 일부입니다.
두 칸은 한 변을 공유할 때 인접한 것으로 봅니다.
격자에는 정확히 25개의 x가 있습니다.
대륙의 개수 $K$ 는 최대 5입니다.
각 테스트 케이스 앞에는 빈 줄이 하나 있습니다.
직사각형과 목표 정사각형은 모두 좌표축에 평행합니다.
여기서 세계는 평면입니다. 즉, 첫 번째 줄과 마지막 줄은 인접하지 않으며, 첫 번째 열과 마지막 열도 인접하지 않습니다.

출력

각 테스트 케이스마다 먼저 케이스 번호를 출력합니다. 직사각형들을 움직여 정사각형을 만들 수 없으면 invalid data를 출력합니다. 만들 수 있으면 필요한 최소 이동 횟수를 출력합니다. 출력 형식은 예시와 같이 Case k: <정답>입니다.

예제2

예제 1

입력

2

....................
....................
....................
....................
....................
....................
..xxxxx.............
..xxxxx.............
....................
....................
..xx..........xxx...
....................
..xxxxx.............
..xxxxx.............
....................
....................
....................
....................
....................
....................

.................x..
....................
....................
....................
..xx................
..xx................
..xx................
..xx................
..xx................
..xx................
.......xxxxxx.......
.......xxxxxx.......
....................
....................
....................
....................
....................
....................
....................
....................

예상 출력

Case 1: 13
Case 2: invalid data

예제 2

입력

1

....................
....................
....................
....xxxxx...........
....xxxxx...........
....xxxxx...........
....xxxxx...........
....xxxxx...........
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

예상 출력

Case 1: 0