雷区布雷的最小值
1.n*n的雷区，分布有x个雷，满足:任意一个格子的相邻格子(不包括斜角)至少有一个地雷。
求x的最小值。
----------------------
2.若为n*m的雷区，求x的最小值。 n*n时是一个奥数题 有难度。。
是不是等价于两种图案覆盖n*n，最少需要多少个的问题？ 可以用暴力法 我考虑过暴力法。
但n＝6时，36个格子，地雷的分布有2^36种。
n再大些，穷举法就难以奏效了。
－－－－－－－－－－
我想了一个折中的方法，先随机确定地雷的分布，是否满足条件。
定出随机条件下得出的最小值s。
然后再穷举地雷个数为s-1下是否有满足条件的分布。
若没有，s就是最小值，若有，再往下减。
虽然工作量减少了，但还是挺大的。不一定适合。 题目有点不确定，确认一下，
有雷的格子是否也要求它的相邻格子里有雷？
如果这样的话，所有的雷会形成一条或多条通路。 有雷的格子和无雷的格子要求一样，都要求相邻格子有雷。 本帖最后由 fengaas 于 2009-9-9 18:33 编辑
如果这样，我觉得两雷相邻组成一组进行覆盖效率最高，形成下面的图形。
1
111
111
1
每一个雷贡献三个空白，即覆盖4个格子。
不过它无法做到整个平面的覆盖，会需要有交叠，从而降低覆盖效率
或者是与它的剪切图一起进行覆盖。
这里的剪切图是指
111
111
1
和
1
11
11
1
它们的覆盖率分别为2.5和2
最终需要多少雷，要根据n的取值来决定。
n越大，边角所占的比率越小，因此覆盖的效率越高
当$n>=3$时
${n^2}/4 < x < {n^2}/2$ 如果n = 2^i
那么n*n需要n个 记n*n的最小值为f(n).
穷举法：
f(2)=2
f(3)=3
f(4)=6
f(5)=9
随机法(未经证实)：
f(6) 14?
f(7) 21?
f(8) 28?
f(9) 37?
页:
[1]
2