堵猫游戏
试试吧。
当在全平面棋盘上玩这个游戏的时候，我们总是可以把猫围在一个特定的区域之内，但是这个游戏提供的范围太小了，好像并不总能够把猫堵死。它类似下面这个经典智力题：
魔鬼在一无穷大棋盘上捕捉天使，设定魔鬼一次能设置1个陷阱（该陷阱可设在任一格子），而天使一次能走1个格子。问魔鬼能否捉住天使？若天使的法力提高到一次能走过N个格子呢？
- Windows游戏中的NP完全问题 上篇文章扫雷是NP完全问题之后，You Xu提到＂不光扫雷是NP 完全问题，空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌...
- 硬币游戏 Alice和Bob两人玩一种硬币游戏。游戏在一个$$2\times2$$的棋盘上进行，棋盘上每个格子上都有一枚硬币。在每一回合，Alice可以决定选择翻转某两枚或者一...
- 取硬币游戏 $$n$$枚硬币排成一排，两人轮流取，每人每次可取其中一枚或者相邻的两枚。 取到最后一枚硬币的赢得游戏。分析游戏策略。 取到最后一枚硬币的算...
- 空当接龙中最难的关 空当接龙可说是最耐玩的Windows小游戏之一，尤其在办公一族中长盛不衰。Win98中的空当接龙有32000局，在XP里面则增加到了 1000000关，不过前32000关与Win9...
- 摸箱子问题以及在Static data structure problems上的应用 以前提到过，理论计算机这门课会邀请一些正在这边访问的教授来讲课，由于是本科生，所以这些教授一般都是讲些有趣的东西，比如之前的overhang 堆...
- Tower Defense游戏盘点 PS1：Work hard, play hard PS2：星际争霸里有一类block的RPG游戏，差不多是诸多RPG里面最流行的。Tow Defense可以视作block RPG游戏的网页版，玩起来更方便。 正...
- 策略游戏：医生和病人（I） 我很早之前就想过这个问题，但一直只知道一个trivial的答案。前两天无意中发现网上已经有高手给出了更好的方案，故记录在此。有兴趣的可以自己想...
- 杀人的理论分析 “杀人”，英文名为"Mafia Game"，广泛流传于国内外。上个星期我们在玩的时候被Elchanan Mossel发现，然后他给了一个talk，内容就是杀人的理论分析。 ...
- 15 puzzle 注：此游戏很有名，有同学问我其算法，我在网上找了一下，居然没多少中文资料，这里按照以前看过的一份答案回忆整理贴出。 游戏规则很简单，4*4...
28条留言 -> 跳到留言表格
有时是可以的
是的 我成功了2次， 要看初始 布局怎样 如果 开始 什么都没有，， 这能围住吗？
什么都没有也能成功
感觉不太可能，要不我当猫你试试看
为什么什么都没有也能成功，感觉不太可能。
原来玩过，诀窍在于往圈大一点，不要一开始就想把猫堵死。
就像生活一样...
挺有意思 玩了两次成功了一次
我还是想知道魔鬼与天使那道题怎么解答
天使与魔鬼那道题 到底天使走的是国际象棋里面的King步还是只能走上下左右？
king步，可以往八个相邻的格子上走。
这个太简单了,我每次都能堵住它,最主要是只在边缘堵,而且要间隔一个再堵.就是隔一个间一个的堵.
有点感觉了
如果在猫周围一格必须要紧密的陷阱才可以阻拦猫
而距离越远越松散的陷阱同样可以起到阻拦的作用
因为猫往那个方向走的时候有足够的时间让陷阱紧密起来
于是大概无限大的空间一定是可以抓住的
一個策略就是估算好貓跑到最近的邊上的距離，然後隔一個格子放一個路障，專門露一個口引誘它（算法也是找缺口的）
這樣就能不浪費太多時間在某個邊上，同時又能預防貓跑到那個漏洞（如果跑到了可以馬上堵住它，這樣又能爭取多一格的時間）
怎麼我的留言不見了，我估計有必勝策略的吧，試了很多盤，都是大概10步就可以把它抓到了……
这游戏太简单了，会下围棋的都知道怎么赢！
此猫还好不会只朝一个方向跑，否则很难抓阿
Ah, nice game. I bet I can even stop the cat if it multiplies every turn to all adjacent cells (except those that are blocked)!
By the way, here's a nice question that I've been trying to solve for a long time, and a solution would be quite publishable: Suppose we're playing a similar game, where the cat multiplies to all adjacent cells (except those that are blocked) at each step. This is called the "firefighter problem". Suppose also that we are allowed to block 1000 nodes at each step. Suppose that the game is played on any planar graph G, not necessarily the hexagonal grid. Suppose that the cat starts at a random location. Prove that we can always trap the cats in a set S of the graph, where the cardinality of S, in expectation, is o(n) (little-oh of n), e.g. this could be O(n/logn). Example: if the graph G is a star, then on average, S can be of size <= 2. (If cat starts at center, lose everything, otherwise lose just one vertex). Zhou Yuan and me (mainly him) can prove this for trees and for outerplanar graphs, even when can block one vertex each turn. We also know this for G with treewidth k, when can block k cells each turn. For planar graphs it's very interesting. Might use the Tarjan-Lipton planar separator theorem, or a variant of it.
嘻，成功了一次
呵，总计成功5次，基数是多少，我就记不清了，有空再来玩
成功几次，都是先在外围画上一个圈
http://bugway.appspot.com/?p=25895
乏味的游戏
找到规律了： 不要跟着猫围堵。而是延猫前进的方向，把最外面的边线封上。则必定可以围住猫。
联系到天使的那个问题，如果天使一次只能走一格，那么魔鬼是必定能抓住天使了。因为魔鬼可以在足够大的范围里面围一个大圈，从而抓住天使。但如果天使法力提高，一次可以走N格，那应该就不能抓住天使了吧？
o(∩_∩)o...哈哈 很容易哦，虽然我总结不出来怎么玩，但还是成功啦！！YEAH
成功了三次，呵呵
成功，有点像下围棋
玩了好几次，成功了一次，这个主要是要看开始的布局，还有就是要远远的吊着，不能急着就把他围住。
按楼上的，确实，画大圈，先圈住，然后小圈子再圈猫，就不会逃脱了，呵呵。
嗯，胜率可以很高。不过不知道是否可以完胜。
我的策略：
假设最下面一行是A，从左往右依次为A1，A2，A3……
那么从下往上倒数第二行分别为B1，B2，B3……
现在假设B1位置有防守子，那么我们防守这周边时候，最好先选择D1，或者A3这样平行四边形对角位置防守，效果最好。
再假设我们选择了A3，那么接下来应该选择B4，总之，就是用平行四边形对角法则进行协防，成功率很高。
成功率80% 感觉很简单