TurnOffLights | Topcoder Archive

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

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

{"0100",
 "1110",
 "0100",
 "0000"}

Returns: 1

Again, a single button press suffices.

```
{"1000",
 "0000",
 "0000",
 "0000"}
```
```
Returns: 2
```
We need to press and hold the lit button, which costs us two moves.
```
{"1100",
 "1000",
 "0000",
 "0001"}
```
```
Returns: 3
```
Press the upper left button (costs 1). Press and hold the lower right button (costs 2).
```
{"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.

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)2024, Topcoder, Inc. All rights reserved.