M-Reachability Charts

Question

Suppose you have an NxN maze with a knight, a princess and an exit.

There is also an evil witch who plans to block M squares (put them under fire). She puts all these blocks on fire before the knight makes his first move (they do not alternate turns).

Given the map in the labyrinth and M, you can decide in O (N ^ 2) whether the Knight can reach the princess, and then exit, for any choice of blocks by the witch (which means - can the Witch make choices that would prevent the Knight and Princess from escaping ?)

Answer 1

This problem is apparently equivalent to determining the presence of M + 1 different paths from the knight to the princess and M + 1 different paths from the princess to the exit. If there are only M distinct paths from the knight to the princess (or the princess to go out), the witch can simply burn one square from each path, blocking the escape (and, alas, any chance of a happy ever romance between them). A.

For example, the maze in your question has two different paths from a knight to a princess and two different paths from a princess to an exit. That way, he can write min(2, 2) to prevent exit.

The number of different paths between two points can be found using the maximum network flow algorithm. Each cell in the grid is a node in the network; two nodes have an edge (bandwidth 1) connecting them if they are adjacent and both are white. The maximum network flow from one point to another is the number of different paths between them.

Ford Fulkerson's algorithm will solve the network flow problem in O(E * f) time, where E is the number of edges in the network (no more than N^2 ) and f is the value of the maximum network flow. Since the maximum network flow does not exceed 4 (the knight has only four possible directions for his first move), the total complexity becomes O(2 * E * 4) = O(N^2) , as requested.

Avoid using node more than once

As others have pointed out, the above solution prevents the use of edges in and out of nodes used more than once; not the nodes themselves.

We can change the flow schedule to avoid using nodes more than once, providing each cell with four input edges, one protective edge and four output edges (each of which has a weight of 1) as follows:

The output edge of one cell corresponds to the input of another. Each cell can now be used for only one path, since the edge of protection can have only stream 1. The sink and source cells remain unchanged. We still have a constant number of edges per cell, leaving the complexity of the algorithm unchanged.