比赛对搜索算法？

Question

我发现了一个有趣对在 http://xepthu.uhm.vn 的配对游戏。规则很简单，你必须要找到并连接两个相同的小宠物，但它们之间的路径没有堵塞，方向不能不能更换3次。让我们来看一个例子：

我已经想了很多有关算法来检查是否有2选定的小宠物之间的路径是有效的，但因为我是个新手，所以我无法找到任何解决方案。你可以建议我一个在C＃中？

Answer 1

这基本上是从图论一个路径寻找问题。在网格中的字段是节点和所有相邻场通过边相连。

路径的发现是一个众所周知的问题，并且有解决这个许多算法。由于您的图形是相当小的，在这里最好的解决方案可能只是蛮力算法。一种流行的路径寻找算法是 Dijkstra算法。

---

<强>蛮力：开始在一些小宠物和探索所有可能的方式，以查看是否一个通向相同的小宠物。可以停止探索的方式，如果方式被阻塞或有2轮以上匝。

您将需要一些“指针”指向在网格中的字段。指针可以移动左，右，向上或向下，条件是在该方向上的场不被阻挡。将指针移动到一个相邻的场。还记得你来自哪里，有多少圈你做出来。重复此，直到你到达目的地。原路返回，如果圈数达到3.确保你不跑在圈子里。

Answer 2

看一看平面图。你将不得不引入第二条件：不超过四个节点可以遍历（开始节点 - 第一方向变化 - 第二方向变化 - 端节点）