Connection Status:
Competition Arena > TurnOffLights

TurnOffLights

SRM 288 · 2006-02-08 · by erinn

SRM 288 · 2006-02-08 · by erinn · Brute Force, Math, Simple Search, Iteration
Class Name: TurnOffLights
Return Type: int
Method Name: fewestMoves
Arg Types: (vector<string>)
Problem Statement

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.

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.

Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TurnOffLights with a public method int fewestMoves(vector<string> board) · 45 test cases · 2 s / 256 MB per case

Submitting as anonymous