시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
IIUM has a street grid of r x c where r represents the number of horizontal streets and c represents the number of vertical streets. Each of the grid cell contains either 0 or 1, where ’1’ represent a light pole and ’0’ represent an empty spot. In each operation you can place a light pole on an empty spot or you can remove a light pole. Your target is to convert the grid in such a way that will meet the following conditions:
Your task is to calculate the minimum number of operation required to accomplish the above conditions.
The first line consist of an integer T where (T ≤1000) represeting the number of test cases. In each test case there will be two integer r and c (1 ≤ r, c ≤ 40) where r is the number of horizontal streets and c represents the number of vertical streets. Each of the next r lines will have c integers each either ’0’ or ’1’.
For each of the test case, the output will be a single line in the following format “Case i: R” where i will be replaced by case number and R will be replaced by the minimum number of steps required to achieve the target grid. If it is not possible to reach the target grid then print −1.
2 2 2 10 00 2 3 010 100
Case 1: 1 Case 2: 2