hdu 4462 第37届ACM/ICPC 杭州赛区 J题

题意:有一块n*n的田，田上有一些点可以放置稻草人，再给出一些稻草人，每个稻草人有其覆盖的距离ri，距离为曼哈顿距离，求要覆盖到所有的格子最少需要放置几个稻草人

由于稻草人数量很少，所以状态压缩枚举，之后慢慢判断即可，注意放稻草人的格子是不需要覆盖的

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt;

 int x[MAXN],y[MAXN],r[MAXN],a[MAXN];

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     while(scanf("%d",&n)!=EOF)

     {

         if(n==)    break;

         scanf("%d",&k);

         for(i=;i<k;i++)    scanf("%d%d",&x[i],&y[i]);

         for(i=;i<k;i++)    scanf("%d",&r[i]);

         int bit=(<<k)-;

         int ans=;

         for(int s=;s<=bit;s++)

         {

             int num=;

             for(j=;j<k;j++)

             {

                 if(s&(<<j))

                 {

                     a[num++]=j; //记录有放稻草人的格子

                 }

             }

             bool vis[MAXN][MAXN],flag=;

             cl(vis);

             for(i=;i<=n;i++)

             {

                 for(j=;j<=n;j++)

                 {

                     for(int d=;d<k;d++)    //没放稻草人的格子

                     {

                         if(i==x[d]&&j==y[d])    vis[i][j]=;

                     }

                     for(int d=;d<num;d++)

                     {

                         if(fabs(i-x[a[d]])+fabs(j-y[a[d]])<=r[a[d]])    //曼哈顿距离

                         {

                             vis[i][j]=;

                             break;

                         }

                     }

                     if(vis[i][j]==)  //说明所有稻草人没法覆盖，该状态方案不可行

                         flag=;

                 }

                 if(flag==) break;  //说明所有稻草人没法覆盖，该状态方案不可行

             }

             if(!flag)continue;

             ans=min(ans,num);

         }

         if(ans>)ans=-;

         printf("%d\n",ans);

     }

 }