首页 > ACM题库 > HDU-杭电 > HDU 4462-Scaring the Birds-状态压缩-[解题报告]HOJ
2015
07-16

HDU 4462-Scaring the Birds-状态压缩-[解题报告]HOJ

Scaring the Birds

问题描述 :

It’s harvest season now!
Farmer John plants a lot of corn. There are many birds living around his corn field. These birds keep stealing his corn all the time. John can’t stand with that any more. He decides to put some scarecrows in the field to drive the birds away.
John’s field can be considered as an N×N grid which has N×N intersections. John plants his corn on every intersection at first. But as time goes by, some corn were destroyed by rats or birds so some vacant intersections were left. Now John wants to put scarecrows on those vacant intersections and he can put at most one scarecrow on one intersection. Because of the landform and the different height of corn, every vacant intersections has a scaring range R meaning that if John put a scarecrow on it, the scarecrow can only scare the birds inside the range of manhattan distance R from the intersection.

The Power of Xiangqi

The figure above shows a 7×7 field. Assuming that the scaring range of vacant intersection (4,2) is 2, then the corn on the marked intersections can be protected by a scarecrow put on intersection (4,2).
Now John wants to figure out at least how many scarecrows he must buy to protect all his corn.

输入:

There are several test cases.
For each test case:
The first line is an integer N ( 2 <= N <= 50 ) meaning that John’s field is an N×N grid.
The second line is an integer K ( 0<= K <= 10) meaning that there are K vacant intersections on which John can put a scarecrow.
The third line describes the position of K vacant intersections, in the format of r1,c1,r2,c2 …. rK,ck . (ri,ci) is the position of the i-th intersection and 1 <= r1,c1,r2,c2 …. rK,ck <= N.
The forth line gives the scaring range of all vacant intersections, in the format of R1,R2…RK and 0 <= R1,R2…RK <= 2 × N.
The input ends with N = 0.

输出:

There are several test cases.
For each test case:
The first line is an integer N ( 2 <= N <= 50 ) meaning that John’s field is an N×N grid.
The second line is an integer K ( 0<= K <= 10) meaning that there are K vacant intersections on which John can put a scarecrow.
The third line describes the position of K vacant intersections, in the format of r1,c1,r2,c2 …. rK,ck . (ri,ci) is the position of the i-th intersection and 1 <= r1,c1,r2,c2 …. rK,ck <= N.
The forth line gives the scaring range of all vacant intersections, in the format of R1,R2…RK and 0 <= R1,R2…RK <= 2 × N.
The input ends with N = 0.

样例输入:

4
2
2 2 3 3
1 3
4
2
2 2 3 3
1 4
0

样例输出:

-1
1

题意:一个n*n的区域,有m个位置是可以放稻草人的,其余都是玉米。对于每个位置(x,y)所放稻草人都有个作用范围ri,即abs(x-i)+abs(y-j)<=r,(i,j)为作用范围内。问至少要在几个位置上放稻草人,才能覆盖所有的玉米,若不可能则输出-1。

题解:可放稻草人位置个数m<=10,所以可以状态压缩(就是枚举0~(1<<m)-1。对于枚举的每个数,表示成m位二进制,从右开始,第几位是1表示放稻草人,否则不放。这样就可以用2^10时间,枚举所有状况,称为状态压缩),枚举所有情况,对于每种情况,遍历所有有玉米的点判断是否可以被覆盖即可。为什么是枚举所有有玉米点而不是广搜,这就是复杂度的问题了,详细在注意事项内。

注意:

1.对于每种情况,如果用光搜,由于没有结束判断,所以要遍历所有的作用范围内的点。以最坏情况记,每种情况都要遍历n^2*k(k为情况中要放稻草人的位置数)次。这种复杂度有点高,至于会不会爆,就没试过了。。而枚举所有玉米点,就只用n^2时间了。

2.还有注意的是,放稻草人的位置不用覆盖。。一开始没发现,wa了3次。。

耗时:0MS

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef __int64 LL;
const int INF=1e9;
const int maxn=3000;
struct node{
    int x,y,r;
 }e[11],f[11];
int ans,map[55][55];
int get_sum(int a)
{
    int s=0;
    while(a)
    {
        if(a&1)s++;
        a=a>>1;
    }
    return s;
}
void find(int x,int n)
{

    int i=0,j,k,t=0,tt;
    tt=get_sum(x);
    if(tt>=ans)return;
    while(x)
    {
        if(x&1)
        {
            f[t++]=e[i];
        }
        x=x>>1;
        i++;
    }
    //cout<<t<<endl;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(map[i][j])continue;
            for(k=0;k<t;k++)
            {
                if(abs(f[k].x-i)+abs(f[k].y-j)<=f[k].r)break;
            }
            if(k>=t)return;
        }
    }
    ans=tt;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)break;
        int i,j,k,m,t,p,q;
        memset(map,0,sizeof(map));
        ans=INF;
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&e[i].x,&e[i].y);
            map[e[i].x][e[i].y]=1;
        }
        for(i=0;i<m;i++)
        scanf("%d",&e[i].r);
        find((1<<m)-1,n);
        //cout<<n<<endl;
        if(ans==INF){printf("-1\n");continue;}
        for(i=0;i<(1<<m);i++)
            find(i,n);
        printf("%d\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/a601025382s/article/details/12277067


  1. 游戏中的扎营设置里没有啊?游戏设置中只能设置友军1/2伤害~没有享受到敌方NPC那样恐怖的减伤啊~而且队友NPC作为敌人的时候就得到那样的减伤了~(┬_┬)