TurningLightOn
SRM 368 · 2007-10-02 · by misof
Problem Statement
A rectangular panel consists of R rows, with C bulbs in each row. The rows are numbered from 0 to R-1, and the columns are numbered from 0 to C-1. Some of the bulbs are turned on and some of them are turned off.
The panel is connected to a board with switches. The switches are arranged into a rectangle with R rows and C columns (i.e., with the same dimensions as the panel).
Flipping each switch will cause some of the bulbs to change state: those that were turned on will become turned off, and vice versa. More precisely, if we flip the switch with coordinates (row,col), then all bulbs with coordinates (x,y) where x<=row and y<=col will change their states. In other words, flipping the switch at (row,col) switches all the bulbs in the rectangle with opposite corners (0,0) and (row,col).
You will be given a
Return the smallest number of flips necessary to have all the bulbs on at the same time.
Notes
- Using the right combination of switches it is always possible to turn on all bulbs at the same time.
Constraints
- board will contain between 1 and 50 elements, inclusive.
- Each element of board will contain between 1 and 50 characters, inclusive.
- All elements of board will have the same length.
- Each element of board will only contain the characters '0' (zero) and '1' (one).
{"0001111",
"0001111",
"1111111"}
Returns: 1
It is enough to flip the switch at (1,2).
{"1111111",
"1111111",
"1111111"}
Returns: 0
Here all the bulbs are already turned on, we don't have to do anything.
{"01001"}
Returns: 3
For this case, one optimal solution is to start by flipping the leftmost switch (turning on the leftmost bulb only), then flip the switch at (0,3) to get "00111", and finally flip the switch at (0,1).
{"0101",
"1010",
"0101",
"1010"}
Returns: 7
For chessboard patterns one needs quite a lot of flips.
{"0"}
Returns: 1
Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TurningLightOn with a public method int minFlips(vector<string> board) · 63 test cases · 2 s / 256 MB per case