雷区布雷的最小值

056254628 · 发表于 2009-9-8 23:28:40

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

1. n*n的雷区，分布有x个雷，满足:
任意一个格子的相邻格子(不包括斜角)至少有一个地雷。
求x的最小值。
----------------------
2. 若为n*m的雷区，求x的最小值。

mathe · 发表于 2009-9-9 09:49:35

n*n时是一个奥数题

wayne · 发表于 2009-9-9 14:00:15

有难度。。

是不是等价于两种图案覆盖n*n，最少需要多少个的问题？

〇〇 · 发表于 2009-9-9 15:36:10

可以用暴力法

056254628 · 发表于 2009-9-9 17:53:38

我考虑过暴力法。
但n＝6时，36个格子，地雷的分布有2^36种。
n再大些，穷举法就难以奏效了。
－－－－－－－－－－
我想了一个折中的方法，先随机确定地雷的分布，是否满足条件。
定出随机条件下得出的最小值s。
然后再穷举地雷个数为s-1下是否有满足条件的分布。
若没有，s就是最小值，若有，再往下减。
虽然工作量减少了，但还是挺大的。不一定适合。

fengaas · 发表于 2009-9-9 18:01:52

题目有点不确定，确认一下，
有雷的格子是否也要求它的相邻格子里有雷？
如果这样的话，所有的雷会形成一条或多条通路。

056254628 · 发表于 2009-9-9 18:06:25

有雷的格子和无雷的格子要求一样，都要求相邻格子有雷。

fengaas · 发表于 2009-9-9 18:32:42

本帖最后由 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$

nlrte13 · 发表于 2009-9-10 16:40:52

如果n = 2^i
那么n*n需要n个

056254628 · 发表于 2009-9-10 19:14:20

记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?

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 雷区布雷的最小值

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。