雷区布雷的最小值

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?

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

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

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