HDU 4462 Scaring the Birds （状态压缩 暴弄）

HDU 4462 Scaring the Birds （状态压缩 暴搞）

题意：给定了一个N*N的地图，地图上有K（0--10）个点可以放守卫，其它点有食物，每个守卫有一个R，只要其它点的食物到守卫点的曼哈顿距离在R范围内就算被保护。

问最少需要多少个守卫，使得所有食物都被保护。

看到K最多只有10，就可以状态压缩K的所有情况，枚举一遍，可行就比较一下。

有个trick：只需要所有的食物被保护就行，空地如果不放守卫未被保护也可以。

#include <iostream>
#include <algorithm>
#include <cmath>
#include<functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 100005
#define INF 0x7FFFFFFF

using namespace std;
int n,k,ans;
int buff[1 << 10];
int vis[55][55];
int mp[55][55];
int dir1[] = {1,1,-1,-1};
int dir2[] = {1,-1,-1,1};
struct node {
    int x,y;
    int r;
} pos[11];

bool inside(int x,int y) {
    if(x > 0 && x <= n && y > 0 && y <= n) return 1;
    return 0;
}

void cover(int id) {
    int x = pos[id].x;
    int y = pos[id].y;
    int r = pos[id].r;
    for(int dx=0; dx<=r; dx++) {
        for(int dy=0; dy<=r-dx; dy++) {
            for(int i=0; i<4; i++) {
                int xx = x + dir1[i] * dx;
                int yy = y + dir2[i] * dy;
                if(inside(xx,yy)) vis[xx][yy] = 1;
            }
        }
    }
}

bool judge() {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(vis[i][j] == 0 && mp[i][j] == 0) return 0;
        }
    }
    return 1;
}

void solve() {
    int total = 1 << k;
    for(int i=0; i<total; i++) {
        memset(vis,0,sizeof(vis));
        int tmp = i;
        int cnt = 0;
        int num = 0;
        while(tmp) {
            if(tmp & 1) {
                num ++;
                cover(cnt);
            }
            tmp = tmp >> 1;
            cnt ++;
        }
        if(judge()) {
            ans = min(ans,num);
        }
    }
    if(ans == INF) printf("-1\n");
    else printf("%d\n",ans);
}

int main() {
    while(scanf("%d",&n) && n) {
        scanf("%d",&k);
        memset(mp,0,sizeof(mp));
        for(int i=0; i<k; i++) {
            scanf("%d%d",&pos[i].x,&pos[i].y);
            mp[pos[i].x][pos[i].y] = 1;
        }
        for(int i=0; i<k; i++) {
            scanf("%d",&pos[i].r);
        }
        ans = INF;
        solve();
    }
    return 0;
}