|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||3||0||0||0.000%|
A rectangular panel consists of R rows, with C bulbs in each row. The rows are numbered from 0 to R-1, and the columns are numbered from 0 to C-1. Some of the bulbs are turned on and some of them are turned off. The panel is connected to a board with switches. The switches are arranged into a rectangle with R rows and C columns (i.e., with the same dimensions as the panel).
Flipping each switch will cause some of the bulbs to change state: those that were turned on will become turned off, and vice versa. More precisely, if we flip the switch with coordinates (row,col), then all bulbs with coordinates (x,y) where x<=row and y<=col will change their states. In other words, flipping the switch at (row,col) switches all the bulbs in the rectangle with opposite corners (0,0) and (row,col).
You will be given a matrix containing the initial states of the bulbs. The character '1' represents a bulb that is turned on, and the character '0' represents a bulb that is turned off.
Calculate the minimum number of flips necessary to have all the bulbs on at the same time.
First line of the input contains T the number of test cases. Each test case starts with a line containing 2 integers R and C. Each of the next R lines contains C character each. These R*C matrix contains the initial state of the bulb. R and C is between 1 and 500 inclusive.
For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is the minimum number of flips necessary to have all the bulbs on at the same time.
6 3 7 0001111 0001111 1111111 3 7 0000000 0000000 0000000 3 7 1111111 1111111 1111111 1 5 01001 1 10 1010101010 4 4 0101 1010 0101 1010
Case #1: 1 Case #2: 1 Case #3: 0 Case #4: 3 Case #5: 10 Case #6: 7