首页 > 代码库 > HDU4462稻草人

HDU4462稻草人

2024-07-13 08:44:31   223人阅读

l问题描述：有一块N*N的玉米田(N<=50),给定K个(X,Y)的坐标位置(K<=10)和相应的覆盖范围，请问，至少在这K个位置中选择几个放置稻草人，能保证玉米田全被覆盖？
 
 
 1 #include<stdio.h> 2 #include<cstring> 3 #include<iostream> 4  5 using namespace std; 6  7 int field[52][52]; 8 int N,K; 9 10 struct Node{11     int x,y,r;12 }node[11];13 14 int abs(int a)15 {16     return a<0?-a:a;17 }18 19 void getField(int k)20 {21     for(int i=1;i<=N;i++)22     {23         for(int j=1;j<=N;j++)24         {25             if(abs(node[k].x-i)+abs(node[k].y-j)<=node[k].r) field[i][j]=1;26         }27     }28 }29 30 bool check()31 {32     for(int i=1;i<=N;i++)33     {34         for(int j=1;j<=N;j++)35         {36             if(field[i][j]==0) return false;37         }38     }39     return true;40 }41 42 int main()43 {44     while(scanf("%d",&N)&&N!=0){45         scanf("%d",&K);46 47         int ans=20;48 49         for(int i=1;i<=K;i++){50             scanf("%d%d",&node[i].x,&node[i].y);51         }52         for(int i=1;i<=K;i++){53             scanf("%d",&node[i].r);54         }55 56         int flag=0,count;57         while(flag<(1<<K)){58             memset(field,0,sizeof(field));59             for(int i=1;i<=K;i++){60                 field[node[i].x][node[i].y]=1;61             }62             count=0;63             for(int i=0;i<K;i++)64             {65                 if(flag&1<<i) {count++;getField(i+1);}66             }67             if(check()&&ans>count) ans=count;68             flag++;69         }70         if(ans<=10) cout<<ans<<endl;71         else cout<<-1<<endl;72     }73     return 0;74 }

 


联系
我们