### 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

*i*

^{th}character in the

*j*

^{th}line signifies that the

*i*

^{th}button in the

*j*

^{th}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)

spencereiron Nov 26, 2015 - 6:53:32 pm UTC Limits