题目链接：传送门
题意：一个n*n的区域，有m个位置是可以放稻草人的，其余都是玉米。对于每个位置(x,y)所放稻草人都有个作用范围ri，
即abs(x-i)+abs(y-j)<=r，，(i,j)为作用范围内。问至少要在几个位置上放稻草人，才能覆盖所有的玉米，若不可能则输出-1。
有一个trick,就是放稻草人的位置不用被覆盖
eg：
input：
2 4
1 1 1 2 2 1 2 2
0 0 0 0
output：
0 0
代码如下：
#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;const int maxn = 60;struct point{int x,y,wide;point(){}point(int _x,int _y):x(_x),y(_y){}}p[maxn];int mp[maxn][maxn];int n,k;bool check(){int tot=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){tot+=(mp[i][j]>0);}return tot==n*n;}bool flag;void modify(point p,int wide,int val){for(int i=max(1,p.x-wide);i<=min(n,p.x+wide);i++)for(int j=max(1,p.y-wide);j<=min(n,p.y+wide);j++){if(abs(i-p.x)+abs(j-p.y)<=wide&&mp[i][j]!=10000)mp[i][j]+=val;}}void dfs(int num,int id,int tot){if(tot>num) return;if(tot==num){if(check())flag=1;return;}if(flag||id>=k) return;modify(p[id],p[id].wide,1);dfs(num,id+1,tot+1);modify(p[id],p[id].wide,-1);dfs(num,id+1,tot);}int main(){while(~scanf("%d",&n)&&n){scanf("%d",&k);for(int i=0;i<k;i++){int x,y;scanf("%d%d",&x,&y);p[i]=point(x,y);mp[x][y]=10000;}for(int i=0;i<k;i++){scanf("%d",&p[i].wide);}int ans = 100000000;for(int i=0;i<=k;i++){memset(mp,0,sizeof(mp));for(int j=0;j<k;j++)mp[p[j].x][p[j].y]=10000;'\&;\\flag = 0;dfs(i,0,0);if(flag){ans = i;break;}}if(ans!=100000000) printf("%d\n",ans);else printf("-1\n");}return 0;}/***422 2 3 31 3422 2 3 31 42 41 1 1 2 2 1 2 20 0 0 0***/
版权声明：本文为博主原创文章，未经博主允许不得转载。
懂得接受失败的人，就是懂得人生真谛的人，
