Create a gist now

Instantly share code, notes, and snippets.

@arukuka /ICPC2017D.java Secret
Created Jul 14, 2017

What would you like to do?
import java.util.*;
public class Main {
Scanner sc = new Scanner(System.in);
int n, m;
String xor(String a, String b) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; ++i) {
if (a.charAt(i) == b.charAt(i)) {
sb.append(0);
} else {
sb.append(1);
}
}
return sb.toString();
}
void run() {
for (; ; ) {
n = ni();
m = ni();
if (n == 0) {
break;
}
String[] b = new String[n];
for (int i = 0; i < n; ++i) {
b[i] = sc.next();
}
String zero = xor(b[0], b[0]);
String xor = zero;
for (int i = 0; i < n; ++i) {
xor = xor(xor, b[i]);
}
HashMap<String, Integer> map = new HashMap<>();
map.put(xor, 0);
Queue<String> queue = new LinkedList<>();
queue.add(xor);
while (queue.size() > 0) {
String node = queue.poll();
// debug(node, map.get(node));
if (node.equals(zero)) {
break;
}
for (int i = 0; i < n; ++i) {
String next = xor(node, b[i]);
if (map.containsKey(next)) {
continue;
}
map.put(next, map.get(node) + 1);
queue.add(next);
}
}
if (map.containsKey(zero)) {
System.out.println(n - map.get(zero));
} else {
System.out.println(0);
}
}
}
int ni() {
return sc.nextInt();
}
public static void main(String[] args) {
new Main().run();
}
void debug(Object... os) {
System.err.println(Arrays.deepToString(os));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment