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

Question

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

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

下面是我的算法(修改后的 BFS)，用于检查迷宫是否可解。它以 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 树的数据结构，它在 O(log n) 时间内支持以下操作:

1. 链接(链接 2 个图节点)
2. 剪切(从图中剪切给定的边)
3. 已连接？ (检查 2 个节点是否由一些边连接)

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

然后所有更新(添加一些节点/删除一些节点)都可以通过删除/添加相邻边来完成，这只需要 O(log(n*m)) 时间

---

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