Submit | All submissions | Best solutions | Back to list |
BTTNS - Buttons |
Luis has a new toy, is a weird board with NxM cells. The cells can be white or black. Each cell has a button inside, when you press a button every cell with Manhattan distance equal or less than K to the cell with the button pressed change of color (white to black, or black to white). At the beginning, every cell is white but somebody pressed some buttons and now the board has some black cells. Help Luis to find how many buttons were pressed. You can assume that no button will be pressed two or more times. There will be always only one configuration of buttons pressed that generate the final board.
Input
The first line of input contains an integer t<=10, the number of test cases. It is followed by t test cases, each consisting of N+1 lines. The first line of each case contains three integers N, M, K separated by space (1 <= N, M <= 20, 0 <= K <= 20). The next N lines contains M integers, each integer can be 0 or 1, the final state of each cell. (0 is white, 1 is black)
Output
For each case, output a single line consisting of the number of buttons pressed.
Example
Input: 2
2 2 0
1 0
0 1
2 2 1
1 1
1 1 Output: 2
4
Added by: | Paulo Costa |
Date: | 2012-01-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | UGTO |
hide comments
2017-12-21 00:09:56 Antonio Roberto Paoli
Just curiosity: How can we know the number of test cases if we donĀ“t have access to then? Last edit: 2018-02-14 23:57:15 |
|
2017-08-23 20:57:18 Thotsaphon Thanatipanonda
number of test cases is 100 not <= 10 |