c++ - 新别墅ACM解决攻略

Question

我正在尝试解决这个 ACM 问题 The New Villa

而且我还没有弄清楚如何解决这个问题，绝对是它的图形问题，但是门和可以切换到其他房间的房间对于制定通用解决方案来说非常困惑。有人可以帮助我定义这个问题的策略吗？另外，我想要一些关于 ACM 问题的讨论论坛，如果您知道，请分享。

谢谢A.S

Answer 1

这似乎是一个关于状态的寻路问题。

您可以用大小为 n 的二进制 vector 表示每个顶点+ 一个标识符 - 你现在所在的房间 [ n是房间数]。

G=(V,E)其中 V = {all binary vectors of size n and a recored for which room you are in}和 E = {(u,v) | you can switch from binary vector u to v by clicking a button in the room you are in, or move to adjacent lights on room }

现在您只需要在可能的路径上运行搜索算法。

可能的搜索算法:

1. BFS - 编程最简单，但运行时间最慢
2. bi - directional BFS - 因为只有一个目标节点，双向搜索将在这里工作，预计会很多比 BFS 更快
3. A* - 找到一个 admissible heurstic function并运行通知 A* 这个问题。它比其他程序更难编程 - 但如果你找到一个好的启发式方法，它很可能会表现得更好。

(*) 以上所有都是完整 [如果存在，将找到一个解决方案] 和最优 [将找到最短的解决方案，如果存在]

(*) 此解决方案以房间数量的指数时间运行，但它应该以 d <= 10 结束。如问题中所示，在合理的时间内完成。