m-Reachability in graphs

Question

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)?

Answer 1

This problem seems to be equivalent to determining if there exists M + 1 distinct paths from the knight to the princess, and M + 1 distinct paths from the princess to the exit. If there are only M distinct 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, where E is the number of edges in the network (at most N^2) and f is 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 becomes O(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.