Problem Statement

You have a rectangle that is divided into a grid of unit squares. The corners and sides of those
squares will be called grid points and grid lines, respectively. Each square contains either a 0 or
a 1. You are given these numbers in a String[] grid. The elements of grid represent the rows of
squares from top to bottom. In each element, the characters represent the squares in that row from
left to right. Each of those characters is either '0' or '1'.

You want to take a walk along some grid lines. The walk must satisfy the following properties:

* You must both start and end the walk in the top left grid point.

* In each step, you have to walk along a single grid line (i.e., move by 1 up, down, left, or right).

* Your walk must visit each grid point at least once.

* Your walk must satisfy the additional property described in the next paragraph.

Consider any walk that satisfies the first three properties. Imagine that a boy is standing in the
middle of a given square and a girl takes the entire walk once (both starting and ending in the top
left grid point). While the girl walks, the boy stays in place but rotates so that he always faces
the girl's current position. Clearly, when the girl ends the walk, the net result for the boy will
be some number of full turns. For each square in the grid, the number written in the square must
correspond to the net number of clockwise turns the boy would make if he stood in that square. (In
other words, if the square contains a 0, the boy standing in that square must rotate by the same
total amount clockwise and counterclockwise, and if the square contains a 1, the boy's total
clockwise rotation must be 360 degrees more than the boy's total counterclockwise rotation.)

You are given the String[] grid. Return the smallest L such that in the given grid there is a valid
walk with L steps, or -1 if no valid walk exists.


Method signature: int findMinimumCycle(String[] grid)
Time limit (s): 2.000
Memory limit (MB): 256


Notes

- The walk may visit each grid point, including the top left grid point, arbitrarily many times.


Constraints

- grid will contain between 1 and 50 elements, inclusive.
- Each element of grid will contain between 1 and 50 characters, inclusive.
- Each element of grid will contain the same number of characters.
- Each character in each element of grid will be either '0' or '1'.


Examples

0)

{"111"}
Returns: 8

The optimal walk is to go around the boundary of the grid clockwise. This gives us a path of length 8.


1)

{"10",
 "11"}
Returns: 10

We need to visit every grid point. Here is one example of an optimal walk.

(figure of a walk that goes around the 1s)

This walk has length 10.


2)

{"111",
 "111",
 "111"}
Returns: 20

The walk must visit every grid point at least once, so only walking along the boundary of this grid is not sufficient.


3)

{"1110000",
 "0000111"}
Returns: 34


4)

{
"1110001110001111111000111",
"1110001110001111111000111",
"1110001110000011100000111",
"1111111110000011100000111",
"1111111110000011100000111",
"1110001110000011100000000",
"1110001110001111111000111",
"1110001110001111111000111"
}
Returns: 364


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.