m-图中的可达性
假设您有一个 NxN 迷宫，其中有骑士、公主和出口。
还有一个邪恶女巫正计划封锁 M 方格（设置他们着火了）。在骑士迈出第一步之前，她会点燃所有这些方块（它们不交替回合）。
给定迷宫的地图和 M，你能在 O(N^2) 内决定骑士是否能够到达公主，然后到达出口，女巫可以选择任何方块（意思是 - 女巫可以到达吗？做出阻止骑士和公主逃跑的选择）？
Suppose you have an NxN maze with a Knight, Princess and Exit.
There is also an evil Witch that is planning to block M squares (set them on fire). She will set all these blocks on fire before the Knight makes his first move (they do not alternate turns).
Given the map to the maze, and M, can you decide in O(N^2) whether the Knight will be able to reach the princess, and then the exit, for any choice of blocks by the Witch (meaning - can the Witch make choices that would prevent the Knight & Princess from escaping)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这个问题似乎相当于确定是否存在从骑士到公主的
M + 1条不同路径，以及从公主到出口的M + 1条不同路径。如果从骑士到公主（或公主退出）只有M条不同的路径，女巫可以从每条路径烧掉一个方块，阻止救援（唉，任何机会）他们之间永远幸福的浪漫）。例如，您问题中的迷宫有两条从骑士到公主的不同路径，以及从公主到出口的两条不同路径。因此，它可以燃烧
min(2, 2)以防止逃逸。可以使用最大网络流量算法找到两点之间的不同路径的数量。网格中的每个单元格都是网络中的一个节点；如果两个节点相邻且均为白色，则它们有一条边（容量为 1）连接它们。从一点到另一点的最大网络流量表示它们之间不同路径的数量。
Ford Fulkerson算法将解决
中的网络流量问题O(E * f)时间，其中E是网络中的边数（最多N^2），f为最大网络流量值。由于最大网络流量最多为 4（骑士的第一步只有四个可能的方向），因此总复杂度变为O(2 * E * 4) = O(N^2)，按要求。避免多次使用节点
正如其他人指出的，上述解决方案可以防止进出节点的边被多次使用；不是节点本身。
我们可以修改流程图以避免节点被多次使用，方法是为每个单元提供四个输入边、一个保护边和四个输出边（每个边的权重为 1），如下所示：
< img src="https://i.sstatic.net/AcjRc.png" alt="细胞图结构图片">
一个细胞的输出边对应于另一个细胞的输入。现在，每个单元只能用于一条路径，因为保护边缘的流量只能为 1。接收单元和源单元保持不变。每个单元的边数仍然恒定，算法的复杂性保持不变。
This problem seems to be equivalent to determining if there exists
M + 1distinct paths from the knight to the princess, andM + 1distinct paths from the princess to the exit. If there are onlyMdistinct paths from the knight to the princess (or princess to exit), the witch can just burn one square from each path, blocking the rescue (and, alas, any chance of a happily-ever-after romance between them).For example, the maze in your question has two distinct paths from the knight to the princess, and two distinct paths from the princess to the exit. Thus, the which can burn
min(2, 2)to prevent escape.The number of distinct paths between two points can be found by using a maximal network flow algorithm. Each cell in the grid is a node in the network; two nodes have an edge (of capacity 1) connecting them if they are adjacent and both white. The maximal network flow from the one point to another represents the number of distinct paths between them.
The Ford Fulkerson algorithm will solve the network flow problem in
O(E * f)time, whereEis the number of edges in the network (at mostN^2) andfis the value of the maximum network flow. Because the maximum network flow is at most 4 (the knight only has four possible directions for his first move), the total complexity becomesO(2 * E * 4) = O(N^2), as requested.Avoiding using a node more than once
As others have pointed out, the above solution prevents edges going into and out of nodes being used more than once; not the nodes themselves.
We can modify the flow graph to avoid nodes being used more than once by giving each cell four input edges, a single guard edge, and four output edges (each having a weight of 1) as follows:
The output edge of one cell corresponds to the input of another. Each cell can now only be used for one path, as the guard edge can only have a flow of 1. Sink and source cells remain unchanged. We still have a constant number of edges per cell, leaving the complexity of the algorithm unchanged.