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

我遇到了一个生成二元维度迷宫的问题r x c (0/false对于阻塞的细胞和1/true免费手机）。每个迷宫都应该是可解决的。

一个人可以从(i, j)到任一(i + 1, j)（向下）或(i, j + 1)（正确的）。求解器预计达到(r - 1, c - 1)（最后一个单元格）从(0, 0)（第一个单元格）。

下面是我的算法（修改后的 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);
}

具体需求：

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

如果多次调用此函数且变化较小，则有一种称为 Link-Cut 树的数据结构，它支持 O(log n) 时间内的以下操作：

1. 链接（链接2个图形节点）
2. 剪切（从图形中剪切给定边）
3. 已连接？ （检查 2 个节点是否由某些边连接）

考虑到网格是一个隐式图，我们可以首先构建 Link-Cut 树，在O(n*m*log(n*m)) time

然后，所有更新（添加一些节点/删除一些节点）都可以通过删除/添加相邻边来完成，这只会花费O(log(n*m)) time

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