首页 > 代码库 > [dfs+水] hdu 4462 Scaring the Birds
[dfs+水] hdu 4462 Scaring the Birds
题意:
N*N的矩阵中有M个点可以放稻草人,且给覆盖距离R
每个稻草人能覆曼哈顿距离R以内的点
问最少需要多少个稻草人
思路:
因为范围很小,直接可以暴力
注意稻草人所在的位置是不需要被覆盖的
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"iostream" using namespace std; int map[55][55]; int n,m; int ans; struct point { int x,y,r; }p[11]; void dfs(int x,int sum) { if(x==m) { int f=1; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(map[i][j]!=0) continue; int k; for(k=0;k<m;k++) { if(map[p[k].x][p[k].y]==-1) continue; if(abs(i-p[k].x)+abs(j-p[k].y)<=p[k].r) break; } if(k==m) { f=0; break; } } if(!f) break; } if(f) ans=min(ans,sum); return ; } dfs(x+1,sum); map[p[x].x][p[x].y]=p[x].r; dfs(x+1,sum+1); map[p[x].x][p[x].y]=-1; } int main() { while(scanf("%d",&n),n) { memset(p,0,sizeof(p)); memset(map,0,sizeof(map)); scanf("%d",&m); for(int i=0;i<m;i++) { scanf("%d%d",&p[i].x,&p[i].y); map[p[i].x][p[i].y]=-1; } for(int i=0;i<m;i++) scanf("%d",&p[i].r); ans=99; dfs(0,0); printf("%d\n",ans==99?-1:ans); } return 0; }
[dfs+水] hdu 4462 Scaring the Birds
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。