c# - 匹配对搜索算法？

Question

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

我想了很多算法来检查任何 2 个选定的 pokemon 之间的路径是否有效，但因为我是新手所以我找不到任何解决方案。你能给我推荐一个用 C# 写的吗？

Answer 1

这基本上是一个来自 graph theory 的寻路问题.网格中的字段是节点，所有相邻的字段由一条边连接。

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

---

蛮力:从一些口袋妖怪开始，探索所有可能的方法，看看是否能找到相同的口袋妖怪。如果一条路被阻塞或超过 2 个转弯，您可以停止探索。

您需要一些指向网格中字段的“指针”。指针可以向左、向右、向上或向下移动，前提是该方向的字段未被阻挡。将指针移至相邻字段。记住你从哪里来，转了多少圈。重复此操作，直到您到达目的地。如果转弯数达到 3，则原路返回。确保您不在原地转圈。