检查二元迷宫是否可通过受限移动解决的有效算法

Question

我遇到了生成尺寸为 r x c 的二进制迷宫的问题（0/false 用于阻塞单元格，1/true 用于空闲单元格）。每个迷宫都应该是可解的。

可以从 (i, j) 移动到 (i + 1, j)（下）或 (i, j + 1)（右）。求解器预计从 (0, 0)（第一个单元格）开始到达 (r - 1, c - 1)（最后一个单元格）。

以下是我的算法（修改后的 BFS），用于检查迷宫是否可解。它的时间复杂度为运行s O(r*c)。我正在尝试以更好的时间复杂度获得解决方案。谁能建议我一些其他算法？我不要路径，我只想看看

#include <iostream>
#include <queue>
#include <vector>

const int r = 5, c = 5;

bool isSolvable(std::vector<std::vector<bool>> &m) {
    if (m[0][0]) {
        std::queue<std::pair<int, int>> q;
        q.push({0, 0});
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.first == r - 1 and p.second == c - 1)
                return true;
            if (p.first + 1 < r and m[p.first + 1][p.second])
                q.push({p.first + 1, p.second});
            if (p.second +1 < c and m[p.first][p.second + 1])
                q.push({p.first, p.second + 1});
        }
    }
    return false;
}

int main() {
    char ch;

    std::vector<std::vector<bool>> maze(r, std::vector<bool>(c));
    for (auto &&row : maze)
        for (auto &&ele : row) {
            std::cin >> ch;
            ele = (ch == '1');
        }

    std::cout << isSolvable(maze) << std::endl;
    return 0;
}

递归求解：

bool exploreMaze(std::vector<std::vector<bool>> &m, std::vector<std::vector<bool>> &dp, int x = 0, int y = 0) {
    if (x + 1 > r or y + 1 > c) return false;
    if (not m[x][y]) return false;
    if (x == r - 1 and y == c - 1) return true;
    if (dp[x][y + 1] and exploreMaze(m, dp, x, y + 1)) return true;
    if (dp[x + 1][y] and exploreMaze(m, dp, x + 1, y)) return true;
    return dp[x][y] = false;
}

bool isSolvable(std::vector<std::vector<bool>> &m) {
    std::vector<std::vector<bool>> dp(r + 1, std::vector<bool>(c + 1, true));
    return exploreMaze(m, dp);
}

具体需求：

我的目标是在我的代码中多次使用这个函数：改变网格的特定点，然后重新检查是否改变了结果。是否有任何记忆的可能性，以便可以重新使用运行中生成的结果？这可以给我更好的平均时间复杂度。

Answer 1

如果多次调用此函数且更改很少，则有一个名为 Link-Cut tree 的数据结构，它支持 O(log n) 时间内的以下操作：

Link（Links 2 个图形节点）
剪切（从图中剪切给定的边）
已连接？（检查 2 个节点是否由一些边连接）

鉴于网格是隐式图，我们可以先构建 Link-Cut 树，在 O(n*m*log(n*m)) 时间内

然后所有更新（添加一些 node/deleting 一些节点）可以仅通过 deleting/adding 个相邻边完成，这将只需要 O(log(n*m)) 时间

虽然我建议优化迷宫生成算法而不是使用这种复杂的数据结构。迷宫生成可以很容易地用 DFS 完成

Answer 2

您正在查看的问题称为 Dynamic Connectivity and as @Photon said, as you have an acyclic graph one solution is to use Link-cut tree. Another one is based on another representation as Euler tour。

Answer 3

在一般情况下你不能低于 O(r*c) 因为，使用任何寻路策略，总会有一个迷宫的特殊情况，你需要遍历尺寸与 [=13= 成比例的矩形子区域] 和 c 才能找到正确的路径。

至于记忆：你可以做一些事情，但可能帮助不大。您可以构建迷宫的副本，但只保留有效路径，并在每个单元格中放入前一个和下一个单元格的方向，以及穿过它的路径数量。让我举例说明。

走下面的迷宫，对应的三个有效路径：

1 1 1 0 1        1 1 1 0 0    1 1 0 0 0    1 1 0 0 0
0 1 1 1 1        0 0 1 1 0    0 1 1 1 0    0 1 0 0 0
0 1 0 1 0        0 0 0 1 0    0 0 0 1 0    0 1 0 0 0
1 1 0 1 0        0 0 0 1 0    0 0 0 1 0    0 1 0 0 0
0 1 1 1 1        0 0 0 1 1    0 0 0 1 1    0 1 1 1 1

您可以构建我称之为前向网格 (FDG)、后向网格 (BDG) 和估值网格的内容：

R B D N N    B L L N N    3 3 1 0 0
N B R D N    N U B L N    0 2 2 2 0
N D N D N    N U N U N    0 1 0 2 0
N D N D N    N U N U N    0 1 0 2 0
N R R R B    N U L B L    0 1 1 3 3

R = right、D = down、L = left、U = up、B = both 和 N = none。 FDG 告诉您，在每个单元格中，有效路径上的下一个单元格在什么方向（或者如果两者都是）。 BDG 反过来也是一样的。估值网格告诉您每个单元格包含多少条有效路径。

为方便起见，我在方向网格中的目的地放置了一个 B。您可以将其视为目标是退出迷宫，为此，您可以从最后一个单元格向任一方向前进。请注意，总是有相同数量的 B 个单元格，并且它恰好是有效路径的数量。

获得这些网格的最简单方法是在深度优先搜索期间构建它们。事实上，您甚至可以将 BDG 用于深度优先搜索，因为它包含回溯信息。

现在您有了这些，您可以阻止或释放一个单元格并相应地更新三个网格。如果将有效路径数也分开保存，则可以同时更新，条件“迷宫可解”变为“有效路径数不为零”。另请注意，您可以组合两个方向网格，但我发现它们分开更容易掌握。

要更新网格和有效路径数，分三种情况：

(A) 您屏蔽了标记为 N 的单元格；你什么都不用做。
(B) 您屏蔽了一个未标记 N 的单元格，因此之前至少是一个有效路径的一部分；根据评估网格中的单元格值减少有效路径的数量，并相应地更新所有三个网格。
(C) 您释放了一个单元格（必须标记为 N）；首先更新所有三个网格，然后通过评估网格中单元格的新值增加有效路径的数量。

更新网格有点棘手，但关键是您不需要更新每个单元格。

在情况（B）中，如果有效路径的数量为零，您可以重置所有三个网格。否则，您可以使用 FDG 向前更新正确的单元格，直到您点击右下角，然后使用 BDG 向后更新正确的单元格，直到您点击左上角。

在情况 (C) 中，您可以先通过进行深度优先搜索来更新方向网格，包括向前和向后，并在您点击未标记的单元格后立即回溯 N （您还需要更新此单元格）。然后，您可以在评估网格中对您点击的单元格的值进行两项总和：一项向前，一项向后。通过新单元格的路径数是这两个总和的乘积。接下来，您可以在更新后的方向网格的帮助下更新估值网格的其余部分。

如果迷宫本身的更新每次都不会创建或中断太多路径，我认为这种技术会对非常大的迷宫的性能产生影响。

检查二元迷宫是否可通过受限移动解决的有效算法

Efficient algorithms to check if a binary maze is solvable with restricted moves

c++

algorithm

maze

graph-theory