[DFS][模拟]hdoj 4462：Scaring the Birds

大致题意：

    在一个n*n的区域，有m个空地，空地上可以放稻草人，每个空地的稻草人有一定的覆盖面积，求最少放多少个稻草人才能覆盖所有的除去空地以外的区域。

 

大致思路：

    由于m很小，所以直接搜索就可以了。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=1000;
int n,m,ans;

struct{
    int x,y,r;
}sum[40];
bool mark[60][60],cov[60][60],tmp[50];
int abs(int a)
{
    if(a>0)return a;
    return -a;
}
bool check()
{
    int i,j,k,r,x,y,top,butt,left,right;
    memset(cov,0,sizeof(cov));
    for(i=1;i<=m;i++)
    {//cout<<m<<endl;
        if(tmp[i])
        {
            r=sum[i].r;
            y=sum[i].y;
            x=sum[i].x;
            top=max(1,y-r);
            butt=min(n,y+r);
            left=max(1,x-r);
            right=min(n,x+r);
            for(k=top;k<=butt;k++)
            {
                for(j=left;j<=right;j++)
                {
                    if(abs(k-y)+abs(j-x)<=r){
                        cov[k][j]=1;
                    }
                }
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(!cov[i][j]&&!mark[i][j])
            {
                return 0;
            }
        }
    }
    return 1;
}

void dfs(int loc,int num)
{
    int i;
    if(num>=ans)return;
    if(loc==m+1)
    {
        if(check())
        {
            ans=min(ans,num);
        }
        return;
    }
    tmp[loc]=1;
    dfs(loc+1,num+1);
    tmp[loc]=0;
    dfs(loc+1,num);
}

int main()
{
    int i,j,k,a,b,c;
    while(cin>>n&&n)
    {
        cin>>m;
        memset(mark,0,sizeof(mark));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&sum[i].y,&sum[i].x);
            mark[sum[i].y][sum[i].x]=1;
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d",&sum[i].r);
        }
        ans=inf;
        dfs(1,0);
        if(ans==inf)ans=-1;
        cout<<ans<<endl;
    }
    return 0;
}