匹配对搜索算法？
我在 http://xepthu.uhm.vn 发现了一个有趣的配对游戏。规则很简单，你必须找到并连接两个相同的神奇宝贝，但它们之间的路径没有被阻塞，并且方向不能改变3次。让我们看一个例子：
我对检查任意两个选定的神奇宝贝之间的路径是否有效的算法进行了很多思考，但因为我是新手，所以我找不到任何解决方案。你能给我推荐一个 C# 语言吗？
I found an interesting pairs matching game at http://xepthu.uhm.vn. The rule is simple, you have to find and connect two identical pokemon but the path between them is not blocked and the direction can't not be changed 3 times. Let's see an example:
I've think alot about the algorithm to check if the path between any 2 selected pokemon is valid but because I'm a newbie so I can't find any solution. Can you suggest me one in C#?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这基本上是一个来自图论的路径查找问题。网格中的字段是节点，所有相邻字段通过边连接。
路径查找是一个众所周知的问题，有很多算法可以解决这个问题。由于您的图表非常小，因此这里最好的解决方案可能只是暴力算法。一种流行的路径查找算法是 Dijkstra 算法。
蛮力：从一些神奇宝贝开始，探索所有可能的方法，看看是否会导致相同的神奇宝贝。如果道路被阻挡或转弯超过 2 个，您可以停止探索该道路。
您需要一些指向网格中字段的“指针”。指针可以向左、向右、向上或向下移动，前提是该方向的字段未被遮挡。将指针移至相邻字段。记住你从哪里来，转了多少圈。重复此操作，直到到达目的地。如果圈数达到 3 就原路返回。确保不要原地踏步。
This is basically a path finding problem from graph theory. The fields in the grid are the nodes, and all adjacent fields are connected by an edge.
Path finding is a well-known problem, and there are many algorithms that solve this. Since your graph is quite small, the best solution here is probably just a brute force algorithm. A popular path finding algorithm is Dijkstra's algorithm.
Brute force: Start at some pokemon and explore all possible ways to see if one leads to an identical pokemon. You can stop exploring a way if the way is blocked or has more than 2 turns.
You'll need some "pointer" pointing to a field in the grid. The pointer can move left, right, up or down, provided that the field in that direction is not blocked. Move the pointer to an adjacent field. Remember where you came from and how many turns you made. Repeat this until you've reached your destination. Backtrack if the number of turns reaches 3. Make sure you don't run in circles.
看一下平面图。您必须引入第二个条件：不能遍历超过四个节点（起始节点 - 第一个方向变化 - 第二个方向变化 - 结束节点）。
Take a look at planar graphs. You will have to introduce a second condition: no more than four nodes may be traversed (start node - first direction change - second direction change - end node).