HDU 4462 Scaring the Birds （暴力求解，二进制法）

题意：给定一个 n*n的矩阵，在一些位置放上稻草人，每个稻草人的范围是一定，问你最少几个能覆盖整个矩阵。

析：稻草人最多才10个，所以考虑暴力，然后利用二进制法，很容易求解，并且时间很少0ms，注意有一个坑，就是那些指定的位置是可以不用覆盖的，

当时WA一次。

代码如下：

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

using namespace std ;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f3f;

const double eps = 1e-8;

const int maxn = 1000 + 5;

const int dr[] = {0, 0, -1, 1};

const int dc[] = {-1, 1, 0, 0};

int m, n;

//int x[55], y[55];

int f[55];

int Find(int x){ return x == f[x] ? x : f[x] = Find(f[x]); }

struct node{

    int r, c, R;

    double d;

    bool operator < (const node &p) const{

        return d < p.d;

    }

};

node a[15];

int ans;

int solve(int s){

    vector<int> v;

    for(int i = 0; i < m; ++i){

        if(s & (1<<i)) v.push_back(i);

    }

    if(v.size() >= ans)  return INF;

    for(int i = 1; i <= n; ++i){

        for(int j = 1; j <= n; ++j){

            bool ok = false;

            for(int k = 0; k < m; ++k)

                if(a[k].r == i && a[k].c == j){  ok = true;  break; }

            if(ok)  continue;

            for(int k = 0; k < v.size(); ++k){

                if(abs(a[v[k]].r-i)+abs(a[v[k]].c-j) <= a[v[k]].R){ ok = true;  break; }

            }

            if(!ok)  return INF;

        }

    }

    return v.size();

}

int main(){

    while(scanf("%d", &n) == 1 && n){

        scanf("%d", &m);

        for(int i = 0; i < m; ++i)

            scanf("%d %d", &a[i].r, &a[i].c);

        for(int i = 0; i < m; ++i)  scanf("%d", &a[i].R);

        ans = INF;

        for(int i = 0; i < (1<<m); ++i){

            ans = min(ans, solve(i));

        }

        printf("%d\n", ans == INF ? -1 : ans);

    }

    return 0;

}