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 ~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 Specification

The input will contain five cases. Each case starts with a line containing two integers ~R~ and ~C~ ~(1 \le R < C \le 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 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.