NSITACMC - LED Board
Amit is getting bored. He has an LED box that can be represented as a rectangular grid of sides, N × M. The LEDs work only in two modes, "ON" or "OFF".
He decides to design a pattern with the LEDs. However, the LED box is peculiar.
In one move, Amit can choose a sub-rectangle of exactly R rows and C columns and toggle the LEDs in that sub-rectangle.
Formally, all LEDs in the subrectangle, which are "ON" change to "OFF" while LEDs that are "OFF" change to the "ON".
Your task is to help Amit determine the minimum number of moves required to make the pattern or output -1 if it is not possible.
Initially, all LEDs are off.
T <= 1000
1 <= N, M <= 300
1 <= R <= N
1 <= C <= M
Input
First line consists of the number of test cases, T.
Then follows T test cases each with the first line N, M, R, C.
Then follows, N lines with exactly M characters denoting the state of the LEDs in the desired pattern.
- 0 - denotes OFF.
- 1 - denotes ON.
Output
T lines each containing the minimum number of moves to establish the pattern or -1 if it is not possible.
Example
Input: 3 3 3 1 1 010 111 011 4 4 2 1 0111 1101 0110 1101 3 4 2 2 0110 0110 0000 Output: 6 -1 1
hide comments
Mukul Gupta:
2013-03-18 04:16:51
@Anon: There is an apparent bug in your solution. It is not just the corner cases. |
|
Anon:
2013-03-18 04:16:51
My code is giving wrong answer. can anybody provide me some special case. My code is working fine on my test cases, may be missing some corner scenario, but i could not find. Can anybody take a look on solution Id 8911153.
|
Added by: | Mukul Gupta |
Date: | 2013-03-14 |
Time limit: | 1.360s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |