Untitled
unknown
plain_text
a year ago
1.4 kB
2
Indexable
Never
import java.util.Scanner; public class Solution { static int n, m, k, res; static int[][] a; static int[] sw; static int countRes() { int dem = 0; for (int i = 0; i < n; i++) { int check = 1; for (int j = 0; j < m; j++) { if ((a[i][j] + sw[j]) % 2 == 0) { check = 0; break; } } if (check == 1) { dem++; } } return dem; } static void backtrack(int col, int count) { // System.out.println(col + " " + count); if (count == k) { int x = countRes(); res = res < x ? x : res; return; } if (col == m) { if ((k % 2 == 0 && count % 2 == 0) || (k % 2 == 1 && count % 2 == 1)) { int x = countRes(); res = res < x ? x : res; } return; } for (int i = 0; i < 2; i++) { sw[col] = i; backtrack(col + 1, count + i); sw[col] = 0; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { n = scanner.nextInt(); m = scanner.nextInt(); k = scanner.nextInt(); a = new int[n][m]; sw = new int[m]; res = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { a[i][j] = scanner.nextInt(); } } backtrack(0, 0); System.out.println("Case #" + t + " " + res); } scanner.close(); } }