POJ 3740 Easy Finding 位运算压缩+DFS

Easy Finding

这道题运用二进制DFS是比较好的方法，当然还可以用dancing links，这个比较高级，先把我看别人的二进制思路然后写的代码贴上来。

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 2000000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
int n, m, bit[18], a[18][303], cnt[303];
bool flag;
void dfs(int num, int in, int out) //in是已经使用的，out是排除了的,num是深度
{
    int i, j;
    if(flag) return; // 找到了就一直return
    if(num >= n) {flag = true; return;} //找到了
    if(cnt[num] == (cnt[num] & out)) return; //如果深搜的目标都在排除的序列中，就return 
    int count = 0;
    for(i = 0; i < m && count < 2; i++)
    if(cnt[num] & in & bit[i]) {j = i; count++;} //如果目标已经使用并且相应位置是1
    if(count == 1) dfs(num + 1, in, out | cnt[num] ^ bit[j]); //则接着搜索时排除除了该1位置以外的1
    else if (count == 0) //还没被使用过
    {
        for(i = 0; i < m && !flag; i++)
        if((cnt[num] & bit[i]) && !(out & bit[i])) // 相应位置是1 并且还没被排除过
        dfs(num + 1, in | bit[i], out | cnt[num] ^ bit[i]); 
    }
}
int main()
{
#ifdef LOCAL
    freopen("ride.in","r",stdin);
    freopen("ride.out","w",stdout);
#endif
    int i, j;
    bit[0] = 1;
    for(i = 1; i < 18; i++) //将不同位置的1预存起来
    bit[i] = bit[i - 1] << 1; 
    while(scanf("%d%d", &m, &n) != EOF)
    {
        memset(cnt, 0, sizeof(cnt));
        for(i = 0; i < m; i++)
        {
            for(j = 0; j < n; j++)
            {
                scanf("%d", &a[i][j]);
                if(a[i][j])
                cnt[j] |= bit[i]; //如果这一个点是1，就将1及其位置存进二进制数组
            }
        }
        flag = false;
        for(i = 0; i < n; i++) //筛掉全是0这个情况
        if(!cnt[i]) break;
        if(i >= n) dfs(0, 0, 0);
        if(flag) puts("Yes, I found it");
        else puts("It is impossible");
    }
    return 0;
}