HDU 4462 DFS

2012 Asia Hangzhou
Regional Contest

给出N*N的矩阵，所有标记为0，当中有K个点标记为1。而且能够在该位置放置一个能够覆盖曼哈顿距离为r的草人。问最少放置几个草人，能够覆盖所有标记为0的点

DFS就可以，注意仅仅须要覆盖标记为0的点

#include "stdio.h"

#include "string.h"

int inf=0x3f3f3f3f;

int n,k,ans;

int x[11],y[11],w[11];

int hash[11];

int map[51][51];

int Fabs(int a)

{

    if (a<0) return -a;else return a;

}

void judge()

{

    int i,j,l,ok;

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

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

        if (map[i][j]==0)

        {

            ok=0;

            for (l=1;l<=k;l++)

                if (hash[l]==1 && w[l]>=Fabs(i-x[l])+Fabs(j-y[l]))

                {

                    ok=1;

                    break;

                }

            if (ok==0) return ;

        }

    i=0;

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

        if (hash[j]==1) i++;

    if (i<ans) ans=i;

}

void dfs(int now)

{

    if (now>k) { judge();return ;}

    hash[now]=1;

    dfs(now+1);

    hash[now]=0;

    dfs(now+1);

}

int main()

{

    int i;

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

    {

        if (n==0) break;

        scanf("%d",&k);

        memset(map,0,sizeof(map));

        for (i=1;i<=k;i++)

        {

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

            map[x[i]][y[i]]=1;

        }

        for (i=1;i<=k;i++)

            scanf("%d",&w[i]);

        ans=inf;

        memset(hash,0,sizeof(hash));

        dfs(1);

        if (ans==inf) printf("-1\n");

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

    }

    return 0;

}