Easy Finding
Description
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.
Input
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.
Output
For each test case, if you could find it output "Yes, I found it", otherwise output "It is impossible" per line.
Sample Input
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
Sample Output
Yes, I found it It is impossible
思路：二进制枚举，再用位运算来判断选的那些行是否满足每列只有一个1，（很神奇的位运算）。考虑最多16行，因此可以用一个int型（32位>16）的每个二进制位来表示每列状态，比如某列的第二行有个1,则int型数字里面第二个二进制位就为1,时间复杂度2^16*m,可以接受。这里存在一个问题就是怎么通过每列的状态（一个int型的数，设为col[j]）来判断这一列是否含有一个1呢？可以这么做,令t = col[j]&i(i表示枚举的行的二进制状态)，这样就把枚举的行里面的1取了出来（是不是狠犀利？！），如果t=0,说明枚举的这些行对应的某列里面一个1都不含，那么就不满足条件，如果t不等于0呢？那么还要考察这列里面是不是只含一个1,可以让t&（t-1）（我靠。。。）,等于0就是一个1,否则不是！
1 #include<cstdio> 2 #include<string> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #define MAXN 333 7 using namespace std; 8 int col[MAXN]; 9 int main(){ 10 int n, m, tmp; 11 freopen("in.c", "r", stdin); 12 while(~scanf("%d%d", &n, &m)){ 13 int flag = 0; 14 memset(col, 0, sizeof(col)); 15 for(int i = 0; i < n; i ++){ 16 for(int j = 0; j < m; j ++){ 17 scanf("%d",&tmp); 18 if(tmp) col[j] += (1 << i); 19 if(i == n-1 && col[j] == 0) flag = 1; 20 } 21 } 22 if(flag){printf("It is impossible "); continue;} 23 for(int i = 1; i < (1 << n); i ++){ 24 int tmp = 0; 25 for(int j = 0; j < m; j ++){ 26 int t = col[j] & i; 27 if(t == 0 || (t & (t-1))) { 28 tmp = 1; 29 break; 30 } 31 } 32 if(!tmp) {flag = 1; break; } 33 } 34 printf(flag == 0 ? "It is impossible ":"Yes, I found it "); 35 } 36 return 0; 37 }