2009 Mock DWITE by A.J.: Problem 4
Lights Out is an electronic game released by Tiger Toys in 1995. (Tiger
Toys was later bought by Hasbro in 1998.) The game consists of an by
grid of lights; when the game starts, some subset (possibly none or
all) of these lights are switched on. Pressing one of the lights will
toggle it and all adjacent to it (up to four). Diagonal neighbours are
not affected. Notice that a light on the edge of the grid will have
fewer than four neighbours. The objective of the game is to solve a
puzzle: switch all the lights off, preferably in as few button presses
as possible. [Wikipedia]
Input Specification
The input will contain five cases. Each case starts with a line
containing two integers and
as described
above. The next
lines contain
characters each. A
0
as the
character in the
line signifies that
the
button in the
row starts out off;
similarly a
1
signifies that the corresponding light starts out on.
Output Specification
For each case given in input, in the order given, print a line
containing a single integer: the minimum number of button presses
required to switch off all of the buttons, or -1
if it is impossible to
switch all the lights off regardless of the number of button presses.
Sample Input (only two cases shown)
3 3
010
111
010
4 5
01000
11010
00001
00110
Sample Output
1
3
Explanation
In the first sample case, pressing the second button in the second row
switches off all lights.
In the second sample case, one presses first the second button in the
second row, then the third button in the third row, then the fourth
button in the third row.
Comments