2013
11-13

# Easy Finding

Given a M×N matrix A. Aij ∈ {0, 1} (0 ≤ i < M, 0 ≤ j < N), could you find some rows that let every cloumn contains and only contains one 1.

There are multiple cases ended by EOF. Test case up to 500.The first line of input is M, N (M ≤ 16, N ≤ 300). The next M lines every line contains N integers separated by space.

For each test case, if you could find it output “Yes, I found it”, otherwise output “It is impossible” per line.

3 3
0 1 0
0 0 1
1 0 0
4 4
0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0

Yes, I found it
It is impossible


//* @author
/**
* @version 2009/08/28
* @author sbzlyessit
*/

import java.io.*;
import java.util.*;

public class Main {

private static StringTokenizer  st;
private static int[] matrix = new int[300];

public static void main(String[] argv) throws Exception {
int  N, M;
int  i, j, x;
boolean found;
N = nextInt();
M = nextInt();
Arrays.fill(matrix, 0);
for (i = 0; i < N; i++)
for (j = 0; j < M; j++)
if (nextInt() == 1)
matrix[j] |= 1 <<  i;
for (found = false, i = (1 <<  N) - 1; !found && i >= 0; i--) {
for (j = 0; j < M; j++) {
x = i & matrix[j];
if (x == 0 || x - (x & (-x)) != 0) break;
}
if (j == M) {
found = true;
System.out.println("Yes, I found it");
}
}
if (!found) System.out.println("It is impossible");
}
}

private static int nextInt() throws Exception {
while (st == null || !st.hasMoreTokens())
}