title: Efficient algorithms to check if a binary maze is solvable with restricted moves
body: <p>I am given a problem to generate binary mazes of dimensions <code>r x c</code> (<code>0/false</code> for blocked cell and <code>1/true</code> for free cell). Each maze is supposed to be solvable.</p>
  <p>One can move from <code>(i, j)</code> to either <code>(i + 1, j)</code>(down) or <code>(i, j + 1)</code>(right). The solver is expected to reach <code>(r - 1, c - 1)</code>(last cell) starting from <code>(0, 0)</code>(first cell).</p>
  <p>Below is my algorithm (modified BFS) to check if a maze is solvable. It runs in <code>O(r*c)</code> 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.</p>
  <pre class="lang-cpp prettyprint-override"><code>#include &lt;iostream&gt;
  #include &lt;queue&gt;
  #include &lt;vector&gt;
  
  const int r = 5, c = 5;
  
  bool isSolvable(std::vector&lt;std::vector&lt;bool&gt;&gt; &amp;m) {
      if (m[0][0]) {
          std::queue&lt;std::pair&lt;int, int&gt;&gt; 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 &lt; r and m[p.first + 1][p.second])
                  q.push({p.first + 1, p.second});
              if (p.second +1 &lt; c and m[p.first][p.second + 1])
                  q.push({p.first, p.second + 1});
          }
      }
      return false;
  }
  
  int main() {
      char ch;
  
      std::vector&lt;std::vector&lt;bool&gt;&gt; maze(r, std::vector&lt;bool&gt;(c));
      for (auto &amp;&amp;row : maze)
          for (auto &amp;&amp;ele : row) {
              std::cin &gt;&gt; ch;
              ele = (ch == '1');
          }
  
      std::cout &lt;&lt; isSolvable(maze) &lt;&lt; std::endl;
      return 0;
  }
  </code></pre>
  <p>Recursive Solution:</p>
  <pre class="lang-cpp prettyprint-override"><code>bool exploreMaze(std::vector&lt;std::vector&lt;bool&gt;&gt; &amp;m, std::vector&lt;std::vector&lt;bool&gt;&gt; &amp;dp, int x = 0, int y = 0) {
      if (x + 1 &gt; r or y + 1 &gt; 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&lt;std::vector&lt;bool&gt;&gt; &amp;m) {
      std::vector&lt;std::vector&lt;bool&gt;&gt; dp(r + 1, std::vector&lt;bool&gt;(c + 1, true));
      return exploreMaze(m, dp);
  }
  </code></pre>
  <p><strong>Specific need:</strong></p>
  <p>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.</p>