http://acm.hdu.edu.cn/showproblem.php?pid=4462
题意：有一个n*n的地图，有k个空地可以放稻草人，给出每个空地可以放的稻草人属性，属性中有个R代表这个位置可以守卫的范围，问最少需要放多少个稻草人才可以守卫这个地图。
思路：可以状态压缩一样枚举所有的状态（为毛昨天想不到），然后就根据这个状态选择哪个空地接着暴力染色地图这样。注意k个地方是空地，不用守卫的。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define M 55 6 #define N 15 7 int mp[M][M], x[N], y[N], r[N], vis[N]; 8 // 可以放稻草人的地方是空地所以不用考虑 9 int main() { 10 int n, k; 11 while(~scanf("%d", &n), n) { 12 scanf("%d", &k); 13 for(int i = 1; i <= k; i++) scanf("%d%d", &x[i], &y[i]); 14 for(int i = 1; i <= k; i++) scanf("%d", &r[i]); 15 int tol = (1 << k), ans = 15; 16 for(int now = 0; now < tol; now++) { // now从0开始 17 memset(vis, 0, sizeof(vis)); 18 int tmp = now, index = 0, cnt = 0; 19 while(tmp) { 20 if(tmp & 1) { vis[k-index] = 1; cnt++; } 21 tmp >>= 1; index++; 22 } 23 memset(mp, 0, sizeof(mp)); 24 for(int i = 1; i <= k; i++) { 25 mp[x[i]][y[i]] = 1; 26 if(vis[i]) { 27 for(int p = 1; p <= n; p++) { 28 for(int q = 1; q <= n; q++) { 29 if(abs(p-x[i]) + abs(q-y[i]) <= r[i]) mp[p][q] = 1; 30 } 31 } 32 } 33 } 34 int flag = 1; 35 for(int i = 1; i <= n && flag; i++) 36 for(int j = 1; j <= n && flag; j++) if(!mp[i][j]) flag = 0; 37 if(flag && cnt < ans) ans = cnt; 38 } 39 printf("%d ", ans == 15 ? -1 : ans); 40 } 41 return 0; 42 }