TopCoder problem "TurnOffLights" used in SRM 288 (Division II Level Three)



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

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Math, Simple Search, Iteration