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

Question

I am given a problem to generate binary mazes of dimensions r x c (0/false for blocked cell and 1/true for free cell). Each maze is supposed to be solvable.

One can move from (i, j) to either (i + 1, j)(down) or (i, j + 1)(right). The solver is expected to reach (r - 1, c - 1)(last cell) starting from (0, 0)(first cell).

Below is my algorithm (modified BFS) to check if a maze is solvable. It runs in O(r*c) time complexity. I am trying to get a solution in better time complexity. Can anyone suggest me some other algorithm?? I don't want the path, I just want to check.

#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;
}

Recursive Solution:

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);
}

Specific need:

I aim to use this function many times in my code: changing certain point of the grid, and then rechecking if that changes the result. Is there any possibility of memoization so that the results generated in a run can be re-used? That could give me better average time complexity.

Answer 1

If calling this function many times with low changes there's a data structure called Link-Cut tree which supports the following operations in O(log n) time:

1. Link (Links 2 graph nodes)
2. Cut (Cuts given edge from a graph)
3. Is Connected? (checks if 2 nodes are connected by some edges)

Given that a grid is an implicit graph we can first build Link-Cut tree, in O(n*m*log(n*m)) time

Then all updates (adding some node/deleting some node) can be done by just deleting/adding neighboring edges which will only take O(log(n*m)) time

---

Though I suggest optimizing maze generation algorithm instead of using this complicated data structure. Maze generation can be done with DFS quite easily