### Problem Statement

You are given a 4x4 game board consisting of buttons which are either lit or unlit. The buttons are numbered 1-16, like so:

1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16

Pressing a button changes the state of that button, along with the states of the buttons to the immediate left, right, top and bottom. Pressing and holding a button, which counts as two moves, changes only the state of that individual light.

The goal of the game is to turn off all of the lights. You are given a String[] board consisting of four elements, each containing four characters. Each character will be a '0' or '1', indicating whether each light is off or on, respectively. You are to return an int indicating the least number of moves necessary to turn off all of the lights.

### Definition

 Class: TurnOffLights Method: fewestMoves Parameters: String[] Returns: int Method signature: int fewestMoves(String[] board) (be sure your method is public)

### Constraints

-board will contain exactly 4 elements.
-Each element of board will contain exactly 4 characters.
-Each character of each element of board will be '0' (zero) or '1' (one).

### Examples

0)

 {"1100", "1000", "0000", "0000"}
Returns: 1
 Press only the button in the upper left corner.
1)

 {"0100", "1110", "0100", "0000"}
Returns: 1
 Again, a single button press suffices.
2)

 {"1000", "0000", "0000", "0000"}
Returns: 2
 We need to press and hold the lit button, which costs us two moves.
3)

 {"1100", "1000", "0000", "0001"}
Returns: 3
 Press the upper left button (costs 1). Press and hold the lower right button (costs 2).
4)

 {"1011", "1010", "0000", "0000"}
Returns: 2
 Here, we push buttons 1 and 3. Notice that button 2 lights up after the first button push, but ends up unlit at the end.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6030

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9809&pm=6030

timmac

#### Testers:

PabloGilberto , brett1479 , Olexiy

#### Problem categories:

Brute Force, Math, Simple Search, Iteration