学步园

题目链接：hdu 4462 Scaring the Birds

题目大意：给定N，表示有一个N∗N的农田，现在有些位置的谷物已经被毁坏，农场主决定在这些位置中选择一些放

置稻草人，给定每个点放置稻草人可以覆盖的曼哈顿距离。求最少放多少个稻草人。

解题思路：题意需要注意，可以放稻草人的位置是没有谷物的。然后对于每个位置预处理出可以覆盖的位置，用bitset

优化即可。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <bitset>
#include <algorithm>

using namespace std;
const int maxn = 55;
const int maxm = 15;
const int inf = 0x3f3f3f3f;

bitset<maxn * maxn> s, p[maxm];

int N, K, R[maxm], C[maxm], D[maxm];
int g[maxn][maxn];

void init () {
    memset(g, 0, sizeof(g));

    scanf("%d", &K);
    for (int i = 0; i < K; i++) {
        scanf("%d%d", &R[i], &C[i]);
        g[R[i]][C[i]] = 1;
    }
    for (int i = 0; i < K; i++)
        scanf("%d", &D[i]);

    for (int i = 0; i < K; i++) {
        p[i].reset();
        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= N; y++) {
                if (g[x][y])
                    continue;
                if (abs(x - R[i]) + abs(y - C[i]) <= D[i])
                    p[i].set( (x-1) * N + y-1);
            }
        }
    }
}

int solve() {
    int ans = inf;

    for (int i = 0; i < (1<<K); i++) {
        int cnt = 0;
        s.reset();

        for (int j = 0; j < K; j++) {
            if (i&(1<<j)) {
                cnt++;
                s |= p[j];
            }
        }

        if (s.count() == N * N - K)
            ans = min(ans, cnt);
    }
    return ans == inf ? -1 : ans;
}

int main () {
    while (scanf("%d", &N) == 1 && N) {
        init();
        printf("%d\n", solve());
    }
    return 0;
}