2009 Mock DWITE by A.J.: Problem 4
Lights Out!
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 R by C 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
The input will contain five cases. Each case starts with a line containing two integers R and C (1 ≤ R < C ≤ 5) as described above. The next R lines contain C characters each. A '0' as the ith character in the jth line signifies that the ith button in the jth row starts out off; similarly a '1' signifies that the corresponding light starts out on.Output
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.
All Submissions
Best Solutions
Point Value: 15 (partial)
Time Limit: 10.00s
Memory Limit: 256M
Added: Sep 26, 2009
Author: amleshjk
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)