首页 > 代码库 > HDU 4462

HDU 4462

2024-07-21 05:32:10   214人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4462

一道题意不清的水题

题意：给一个n*n的格子，在上面放草人，每个草人有恐惧范围，问最少选择几个草人可以覆盖所有格子

解法：草人个数只有10，暴力即可，dfs或者状压枚举。距离指的是曼哈顿距离，已经有草人的格子，不管你选不选都是不用计算的

注意：可能有0的情况，即所有格子放满草人

#include <iostream>#include <cstdio>#include <cstring>using namespace std ;int r[15],c[15],a[15],R[15] ;int vis[55][55] ;int ABS(int x){    return x>0?x:-x ;}int main(){    int n,k ;    while(~scanf("%d",&n),n)    {        scanf("%d",&k) ;        memset(vis,0,sizeof(vis)) ;        for(int i=0 ;i<k ;i++)        {            scanf("%d%d",&r[i],&c[i]) ;            vis[r[i]][c[i]]=1 ;        }        for(int i=0 ;i<k ;i++)            scanf("%d",&R[i]) ;        if(k==n*n)        {            puts("0") ;            continue ;        }        int s=(1<<k) ;        int ans=0xfffffff ;        for(int i=0 ;i<s ;i++)        {            int st=0 ;            for(int j=0 ;j<k ;j++)            {                if(i&(1<<j))a[st++]=j ;            }            int flag ;            for(int j=1 ;j<=n ;j++)            {                for(int h=1 ;h<=n ;h++)                {                    if(vis[j][h])continue ;                    flag=0 ;                    for(int l=0 ;l<st ;l++)                    {                        if(ABS(j-r[a[l]])+ABS(h-c[a[l]])<=R[a[l]])                        {                            flag=1 ;                            break ;                        }                    }                    if(!flag)break ;                }                if(!flag)break ;            }            if(!flag)continue ;            ans=min(ans,st) ;        }        if(ans==0xfffffff)puts("-1") ;        else printf("%d\n",ans) ;    }    return 0 ;}
View Code

 

HDU 4462


联系
我们