hdu4462--曼哈顿距离

题目大意：有N*N个点的田野,然后有k个点是用来放稻草人的，每个稻草人对周围满足曼哈顿距离的庄稼有保护作用

问最小的稻草人的个数能够保护所有庄稼,如果不能保护则输出-1

注意的地方：

1.放稻草人的点不需要计算，因为不是庄稼

2.可能存在0的解，也就是k=N*N时

思路：二进制枚举所有情况,找到最小解

代码如下:

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

using namespace std;

const int maxs = 51;

int n,k;

bool vis[maxs][maxs];

struct Point

{

   int x,y;

   int dis;

}point[11];

bool judge(Point p[],int t,Point goal)

{

    for(int i=0;i<t;i++)

        //满足曼哈顿距离的条件

        if(fabs(p[i].x-goal.x)+fabs(p[i].y-goal.y)<=p[i].dis)

            return true;

    return false;

}

bool solve(Point p[],int t)

{

    memset(vis,false,sizeof(vis));

    for(int i=0;i<k;i++)

        vis[point[i].x][point[i].y]=true;

    Point goal;

    for(int x=1;x<=n;x++)

        for(int y=1;y<=n;y++)

            if(!vis[x][y])

            {

                goal.x=x; goal.y=y;

                if(!judge(p,t,goal))

                    return false;

            }

    return true;

}

int main()

{

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

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

    {

        int ans = 20;//因为最大为10

        scanf("%d",&k);

        for(int i=0;i<k;i++)

            scanf("%d%d",&point[i].x,&point[i].y);

        for(int i=0;i<k;i++)

            scanf("%d",&point[i].dis);

        if(k==n*n)

        {

            printf("0\n");

            continue;

        }

        int total = 1<<k;

        //二进制枚举

        for(int i=1;i<total;i++)

        {

            int temp;

            Point p[11];

            memset(p,0,sizeof(p));

            int cnt=0;

            for(int j=0,s=1;j<k;j++)

            {

                if(i&s)

                    p[cnt++]=point[j];

                s=s<<1;

            }

            if(solve(p,cnt))

            {

                temp=cnt;

                if(temp<ans)

                    ans=temp;

            }

        }

        if(ans==20)

            printf("-1\n");

        else

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

    }

}