匹配成对搜索算法？

Question

我在http://xepthu.uhm.vn找到了一对有趣的配对游戏。规则很简单，你必须找到并连接两个相同的口袋妖怪，但它们之间的路径不被阻塞，方向不能改变3次。让我们来看一个例子：

alt text http://img14.imageshack.us/img14/382/16170399.png

我有很多思考的算法来检查是否有2选定的小宠物之间的路径是有效的，但因为我是个新手，所以我无法找到任何解决方案。你能用C＃建议我吗？谢谢。

Answer 1

这基本上是从graph theory找到问题的路径。网格中的字段是节点，并且所有相邻的字段都通过边连接。

路径查找是一个众所周知的问题，并且有很多算法可以解决这个问题。由于您的图形非常小，因此这里最好的解决方案可能只是一个蛮力算法。流行的路径搜寻算法是Dijkstra's algorithm。

---

蛮力：开始在一些小宠物，并寻求一切可能的方式，查看是否会导致相同的宠物小精灵。如果途中被阻挡或者超过2回合，你可以停止探索。

你需要一些指针指向网格中的一个字段。指针可以向左，向右，向上或向下移动，前提是该方向上的字段未被阻止。将指针移到相邻的字段。记住你来自哪里以及你制作了多少回合。重复此操作直到您到达目的地。如果圈数达到3，则返回。确保您不以圆圈运行。

Answer 2

看看平面图。您将不得不引入第二个条件：不得超过四个节点（起始节点 - 第一个方向更改 - 第二个方向更改 - 最终节点）。