search

lampTurn on the Lights

https://www.facebook.com/codingcompetitions/hacker-cup/2011/round-1a/problems/B

hashtag
Question

A simple game consists of a grid of RxC buttons. Each button will be either lighted, or unlighted. Whenever you push a button, the state of that button, and its (up to) four neighbors will toggle -- lighted buttons will become unlighted and unlighted buttons will become lighted. Note that the neighbors do not 'wrap' and thus a corner button has only two neighbors, while an edge button has three.

In this problem you will be given an initial configuration of the buttons. Your task is to push the right buttons so that, when you are done, all of the lights are turned on. If there are multiple ways to do this, you should determine the minimum number of buttons pushes that it can be done in.

hashtag
Input Format

You will first read an integer N the number of test cases. For each test case, you will read two integers R and C. This will be followed by R whitespace-separated tokens, each containing C characters. A 'X' indicates a lighted button, while a '.' indicates an unlighted button.

hashtag
Constraints

N=20N = 20
1≀R,C≀181 \le R, C \le 18

hashtag
Output Format

For each test case you should output the minimum number of button presses required to turn on all the lights. If there is no way to do this, you should output -1.

hashtag
Sample Inputs:

hashtag
Input

hashtag
Output

chevron-rightSolutionhashtag

PreviousDiversity NumberNextWine Tasting

Last updated