Containing Zombies and Respecting Building Codes
It's well documented that the only way to thwart zombies is to trap them in closed fences. Zombie hunters have for years been luring zombies into clear spaces and then erecting such fences at lightning speeds so they can't go very far.
Unfortunately, government has its zoning laws, its taxes, and its building codes, and recently they started to enforce silly constraints on how these zombie-enclosing fences can be constructed. According to city codes, fence posts must be planted at regular intervals, and the fences themselves must respect arbitrary limits on how many walls can surround a unit square of land. We also want to build as long of an enclosing fence as possible, because the government has plenty of money to waste on such things.
Building Zombie Fences
×
Build walls between vertices to form a single enclosed fence without crossings or branches. The number indicates exactly how many walls - according to the crazy city building laws - must surround it (and a lack of number means there's no constraint.) So, presented with the following 55 grid of land squares:
the following fence could be constructed:
-1
The grid of lots is always n×n (1 ≤ n ≤ 6), and each lot is either a number (0, 1, 2, or 3) to impose a constraint, or a blank if no constraint is being imposed. You're to output the length of the longest possible loop (or equivalently, the number of vertices in the loop), or " if no loop exists. Note that loops of length 0 are invalid. A valid loop must enclose a non-zero amount of area.
Input
-
The input is a series of zombie fencing problems, expressed by n, the dimension of the problem, followed by an n×n grid (1 ≤ n ≤ 6) with the number constraints (with the " to represent no constraint), followed by a blank line. End of input is marked by a single '0'.
Output
For each fence problem, you should print the length of the longest fence loop that can be constructed for that problem while still respecting all constraints, or you should print '-1' if the problem has no such solution. There should be no extraneous white space, save for the newlines that separate each of the fence lengths.