首页 > 代码库 > HDU4462稻草人
HDU4462稻草人
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。