題目大意：
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.
代碼寫得不好看，速度一般，200+ms
#include <stdio.h>
#include <string.h>
int M, N, T;
unsigned short arr[320];
int dfs(int idx, unsigned short ban, unsigned short sel)
{
int i;
unsigned short mask;
if (idx == N)
return 1;
mask = sel & arr[idx];
if (mask & (mask - 1))
return 0;
if (mask)
return dfs(idx + 1, (ban | arr[idx]) & ~mask, sel);
for (i = 0; i < M; i++) {
mask = 1 << i;
if (ban & mask)
continue;
if (!(arr[idx] & mask))
continue;
if (dfs(idx + 1, (ban | arr[idx]) & ~mask, sel | mask))
return 1;
}
return 0;
}
int main()
{
int i, n, m;
freopen("e:\\test\\in.txt", "r", stdin);
while (scanf("%d%d", &M, &N) != EOF) {
memset(arr, 0, N*2);
for (m = 0; m < M; m++) {
for (n = 0; n < N; n++) {
scanf("%d", &i);
if (i)
arr[n] |= 1 << m;
}
}
printf(dfs(0, 0, 0) ? "Yes, I found it\n" : "It is impossible\n");
}
return 0;
}