魔方吧·中文魔方俱乐部

标题: 魔鬼捉天使 [打印本页]

作者: 华容道 时间: 2011-6-7 16:24:38 标题: 魔鬼捉天使

魔鬼在一无穷大棋盘上捕捉天使（魔鬼和天使都足够聪明），魔鬼一次能设置1个陷阱（该陷阱可设在除天使所在格子外任一格子），而天使一次只能走1个格子（即走到相邻的格子，但不可斜行），当天使无法行走时就可以被魔鬼捉住，问魔鬼能否捉住天使？若魔鬼可以捉住天使，至少需设置多少个陷阱？
拓展：如果天使可以斜行（与国际象棋中的王走法相同），其它条件不变，结果又会如何？
附一个“抓猫”的flash小游戏，可以从中找找灵感：

http://www.gamedesign.jp/flash/chatnoir/chatnoir.swf

[ 本帖最后由华容道于 2011-6-14 06:00 编辑 ]

附件: 20090613_50c2bed15f7f5d371b99xK51sKbg3jgH.gif (2011-6-7 16:24:38, 8.83 KB) / 下载次数 112
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ2NjQwfGNjNTBhNTkxfDE3NjEzMjk2NTJ8MHww

作者: cbfcbf 时间: 2011-6-7 16:29:08

俺居然也沙发,呵呵

作者: 葙對。。★ 时间: 2011-6-7 16:29:16

如果天使往一个方向一直走，棋盘无限大，那么魔鬼不就抓不住天使了？？？

作者: 葙對。。★ 时间: 2011-6-7 16:31:12

不好意思，没看清题目，是可以抓到的

作者: danielsun 时间: 2011-6-7 16:33:08

魔鬼一次方一个陷阱，类似于围棋的一种下法，结果是天使永远不会被魔鬼抓住。
魔鬼一次下两个陷阱就可以抓住天使。
如果天使可以斜行，没有论证过，我猜至少魔鬼一个需要4个陷阱

作者: 耗子哥哥 时间: 2011-6-7 16:37:35

感觉类似这个：

http://www.ziyiblog.cn/upload/cat.swf

[ 本帖最后由耗子哥哥于 2011-6-7 16:38 编辑 ]

作者: 华容道 时间: 2011-6-7 16:53:33

楼上的图片无法显示。

作者: 葙對。。★ 时间: 2011-6-7 16:56:18

耗子哥你那个都是空白的

作者: 轩恒 时间: 2011-6-7 18:22:16

怎么能抓住啊？
不可能吧？

作者: 骰迷 时间: 2011-6-7 19:20:20

如图放陷阱
橙色代表初始位置,红色是完结位置

附件: 天使.jpg (2011-6-7 19:20:20, 20.21 KB) / 下载次数 109
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ2NzA2fDYyMDFmOTE4fDE3NjEzMjk2NTJ8MHww

作者: 骰迷 时间: 2011-6-7 19:22:29

斜放猜想捉不到

作者: lulijie 时间: 2011-6-7 19:57:06

把陷阱放在远离魔鬼的地方，等魔鬼还没走到此处的时候，已经在此处串成了一条壕沟；如果魔鬼改向，陷阱也改为放在魔鬼前进方向的远处。这样就很可能在远处陷阱围成了一圈，那么魔鬼再也走不出去了。
问题是为了使得陷阱数最少，这个第一次放的有多远要仔细斟酌。

作者: lulijie 时间: 2011-6-7 19:59:22

并且这个壕沟不需要摆成密不透风，可以中间有一个一个的缺口，魔鬼靠近的时候能把它堵上就行了。

作者: 骰迷 时间: 2011-6-7 20:29:09 标题: 回复 12# 的帖子

你认为斜走能堵住吗?

作者: lulijie 时间: 2011-6-7 21:08:24

回14#：
我觉得还是很有可能堵上的

作者: 华容道 时间: 2011-6-7 21:48:35 标题: 回复 12# 的帖子

这个思路很好！

天使捉魔鬼，

。

作者: 骰迷 时间: 2011-6-7 22:18:01

不如先解决这个吧:天使只能斜走.
比较难抓

作者: 骰迷 时间: 2011-6-7 22:33:09

斜走则大概这样抓
灰色为陷阱

附件: 天使2.jpg (2011-6-7 22:33:09, 86.18 KB) / 下载次数 74
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ2Nzg5fGY2ZjgzZjZlfDE3NjEzMjk2NTJ8MHww

作者: 骰迷 时间: 2011-6-7 22:35:10

斜走具奇偶性,如果加上横走直走就真的很麻烦了,我用围棋试演了一下抓不到自己.

作者: 骰迷 时间: 2011-6-7 22:54:52

想了一下,如果天使只能直走因其行走距离短,因此即使在围堵处漏空也可以有足够步数等天使过来才堵住,更因为漏空堵塞的方法走得很快,能够抢在天使前面迫使他拐弯(10楼);
如果天使只能斜走,因其奇偶性致只需要堵塞仅有的几个可能性,另外陷阱位置可以跟天使相邻(指一步横一步直即可到达),使得魔鬼可以抢先包围天使(18楼).
当天使能任意方向走动时,便很难漏出空位使得既能抢先,又能确保够步数填洞.应该如何安排漏空位置呢?
又或者无解?

作者: 暴力打开 时间: 2011-6-12 09:18:09

话说只能斜走不是等价于只能直走吗？

作者: Cielo 时间: 2011-6-12 11:05:07 标题: 回复 6# 的帖子

不知耗子哥哥发的什么图……

不过之前在方方的itouch上玩过一个游戏，貌似规则就和楼主说的一样~

作者: 骰迷 时间: 2011-6-12 11:47:40 标题: 回复 21# 的帖子

好像终于被人发现了
那么究竟能不能封住?

作者: mowxqq 时间: 2011-6-12 17:20:19

定义天使的初始位置为原点。
现假设天使行走前不存在陷阱，最优走法“之”字形走到点(m,n)需|m|+|n|步，此时魔鬼也走了|m|+|n|步，而要栏住天使至少要放置|m|+|n|+1步，魔鬼始终落后于天使。
要拦住天使，在天使行走前至少要存在4个陷阱，4个象限各一点或4坐标轴上各一点
斜走的情况只要把坐标轴旋转45度即同上。

作者: 骰迷 时间: 2011-6-13 13:26:43

其实我想问下我的置顶精华帖怎么没有了

作者: 石崇的BOSS 时间: 2011-6-13 22:18:50

直走和加上斜走应该能抓住的，在前方设置就可以了，但是最少数值计算有难度，记得和以前玩过一个叫“圈猫”的游戏类似

作者: mowxqq 时间: 2011-6-14 08:36:19

就如抓猫的游戏，初始已经设好若干个陷阱。如果初始没有陷阱请抓给我看看！难度恐怕是在陷阱的初始个数和排布吧。

作者: 华容道 时间: 2011-6-14 11:10:37 标题: 回复 27# 的帖子

地图太小，初始没有陷阱根本抓不住。

作者: tm__xk 时间: 2011-6-14 12:46:39

难道这题已经有解了咩..

作者: wpolly 时间: 2011-6-15 06:56:47

已经有解了。。
天使只能直走的时候魔鬼可以在8x8的范围内抓住他
能斜走的时候可以在35x35的范围内抓住

具体解答可以参考一本书《Winning ways for your mathematical plays》 (有中译本《稳操胜券》) 的第19章

[ 本帖最后由 wpolly 于 2011-6-15 06:59 编辑 ]

作者: 华容道 时间: 2011-6-15 07:13:33 标题: 回复 30# 的帖子

谢谢，我下载个电子书看看

作者: tm__xk 时间: 2011-6-15 09:18:00

呃..我有一种电脑很可能有这本书的感觉....

作者: jingyucan 时间: 2014-3-27 20:30:29

用围棋的夹吃可以在15次之内抓住天使

作者: 阿不思 时间: 2014-3-28 15:04:04

耗子哥哥发表于 2011-6-7 16:37
感觉类似这个：

看不到!!!

作者: 阿不思 时间: 2014-3-28 15:05:37

danielsun 发表于 2011-6-7 16:33
魔鬼一次方一个陷阱，类似于围棋的一种下法，结果是天使永远不会被魔鬼抓住。
魔鬼一次下两个陷阱就可以抓 ...

不,我认为魔鬼一行一行全放满,就ok了!

作者: 阿不思 时间: 2014-3-28 15:06:38

骰迷发表于 2011-6-7 19:20
如图放陷阱
橙色代表初始位置,红色是完结位置

高手!!!!!!!!!!

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)