这个问题似乎相当于确定是否存在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），如下所示：
一个单元的输出边缘对应于另一个单元的输入。现在，每个单元只能用于一条路径，因为保护边缘的流量只能为 1。接收单元和源单元保持不变。每个单元的边数仍然恒定，算法的复杂性保持不变。