## ICPC PACNW 2010 I Zombie Fences 2: Electric Boogaloo

View as PDF

Points: 40 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
C, C++, Java, Pascal

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 5 x 5 grid of land squares:

the following fence could be constructed:

The grid of lots is always , where (we actually don't know what's the largest that can be done in a second, so will keep on cranking it up as better solutions come in and update: current max is 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 -1 if no loop exists. Note that loops of length 0 are invalid. A valid loop must enclose a non-zero amount of area.

There are currently 6 subtasks present. Subtask contains only tests where . You will receive marks for solving subtask . To get credit for subtask , you must correctly solve subtask .

The data currently consists of just the original data used at the ICPC regional, which had the added constraint that , though this is not an important constraint for the problem.

#### Input

The input is one zombie fencing problems, expressed by and , the dimensions of the problem, followed by an grid with the number constraints (with the – to represent no constraint).

#### Output

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.

#### Sample Input

2 2
22
22

#### Sample Output

8

#### Sample Input

5 5
----0
2---2
3--2-
2-2--
22---

#### Sample Output

32