문제
오직 0과 1만으로 이루어진 m*n 크기의 행렬이 있습니다. 그 중 다음 조건을 만족시키는 행렬을 “바둑판 행렬”이라고 부릅니다.
어떤 크기 m인 배열 A[1…m]와 크기 n인 배열 B[1…n]가 존재하여 행렬의 i 행 j 열의 원소를 aij 라 할 때, 모든 i, j(1 ≤ i ≤ m, 1 ≤ j ≤ n)에 대해 aij = A[i] xor B[j]을 만족한다.
예를 들어, 아래 행렬들은 “바둑판 행렬”입니다.
1 0 0 1
0 1 1 0
1 0 0 1
0 0
0 0
1 0 1 1 0
0 1 0 0 1
0 1 0 0 1
가온이에게는 0과 1만으로 이루어진 행렬이 있습니다.
가온이는 이 행렬의 어느 원소를 골라 바꾸는 시행을 최대 k번 시행할 수 있습니다. 가온이는 이 시행을 최소로 하여 “바둑판 행렬”을 만들고 싶어합니다. 만약 k번 안에 가능하다면 이 시행의 최솟값을, 불가능하다면 “-1”을 출력하세요.
입력
여러분이 문제를 풀지 않고 printf(“-1”)으로 점수를 얻는 것을 방지하기 위해, 각 입력은 몇 개의 테스트로 구성됩니다. - 첫 번째 줄에는 테스트케이스의 개수인 T(T<=10)가 주어집니다.
각 테스트 케이스에 대해, - 첫 번째 줄에 가온이가 가진 행렬의 가로 및 세로 크기인 m과 n, 그리고 원소를 골라 바꾸는 시행의 최대값인 k가 주어집니다.
- 그 후 m개의 줄에 행렬의 원소를 나타내는 n개의 수가 주어집니다. i번째 줄의 j번째 수는 a_ij를 나타냅니다.
출력
각 테스트 케이스에 대해, 원소를 바꾸는 시행의 최솟값 또는 -1을 출력합니다. - 데이터의 10%는 1 <= n, m <= 4, k <= 10 - 나머지에서 20%는 1 <= n, m <= 10, k <= 2 - 나머지에서 30%는 1 <= n, m <= 10, k <= 10 - 나머지 40%는 1 <= n, m <= 100, k <= 10
첫 번째 테스트케이스를 바둑판 행렬로 만들기 위해서는 a_22와 a_33을 1로 만들어야 하는데, k가 1(<2)이므로 -1을 출력합니다.
두 번째 테스트케이스에서는 a_32, a_33을 바꾸어서 1 0 0 0 0 1 1 1 1 0 0 0 으로 만들면 “바둑판 행렬”이 됩니다. 세 번째는 a_34를 1로 바꾸면 됩니다.
예제
3
4 4 1
1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
3 4 3
1 0 0 0
0 1 1 1
1 1 1 0
3 4 2
1 0 0 1
0 1 1 0
1 0 0 0
-1
2
1
로그인해야 코드를 작성할 수 있어요.