Coalescing Continents#3101
Continental drift refers to the idea that once the Earth's continents were all in one piece and, with time, they drifted away from each other to their present positions.
In this problem, we are concerned with the reverse process — Continental Coalesce.
For the sake of simplicity, let us assume that the continents were initially merged together, forming a square. With time, the square disintegrated into different continents in the shape of rectangles and drifted away from their original position.
You are provided with the current locations of the continents (i.e., rectangles). These locations have been outlined with the help of satellites. Your first task is to determine whether the provided data is valid. The data is valid if you can move the rectangles to form a square. In one move, you can pick any rectangle and push it one unit in one of the four directions (north, south, east, or west). The continents may slide underneath one another during movement — that is, more than one continent can occupy the same position at the same time. If it is possible to form a square, you are also required to find the minimum number of moves needed to accomplish this. The final position of the square does not matter. Note that in the final position, no two continents can overlap and the resulting square must not have any empty cells.
The first line of input is an integer (T \leq 200) indicating the number of test cases. Each case consists of lines, each containing characters. Each character is either a dot (.) representing an empty space, or an (ASCII value ). Every character is part of some continent.
Notes:
In the input grid, characters from different continents are not adjacent to each other. Each belongs to a rectangle.
Two cells are adjacent if they share a common edge.
There are exactly characters in the grid.
The number of continents, , is at most .
There is a blank line before each test case.
The rectangles and the target square are axis-aligned.
The earth here is flat. That is, the first and last row are NOT adjacent. The same applies to the first and last column.
For each case, output the case number. If it is not possible to form a square by moving the rectangles, output "invalid data", with quotes for clarity. If it is possible, output the minimum number of moves required.
Example 1