c# - 匹配对搜索算法？

Question

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

我已经考虑了很多关于检查任何 2 个选定口袋妖怪之间的路径是否有效的算法，但是因为我是新手，所以我找不到任何解决方案。你能给我推荐一个 C# 吗？

Answer 1

这基本上是图论中的寻路问题。网格中的字段是节点，所有相邻的字段由一条边连接。

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

---

蛮力：从一些口袋妖怪开始，探索所有可能的方法，看看一个人是否会导致相同的口袋妖怪。如果道路被阻挡或超过 2 个转弯，您可以停止探索。

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

Answer 2

看看平面图。您将不得不引入第二个条件：最多可以遍历四个节点（起始节点 - 第一个方向变化 - 第二个方向变化 - 结束节点）。