Algorithm (Recursion)

1. Let $f(r, c, V)$ denote the number of ways to reach the destination when starting from $r, c$ and visited set stored in $V$(which contains $(r, c)$).
2. Note that we have
   $$ f(r, c) = \begin{cases} \sum_{(nr, nc) \in \text{unvisited neighrbors($r ,c$)}} f(nr, nc, V\cup \{nr, nc\}) & \text{if } (r, c) \neq \text{destination} \\\\ 1 & \text{if } (r, c) = \text{destination} \text{ and $V$ covers all walkable nodes} \\\\ 0 & \text{if } (r, c) = \text{destination} \text{ and $V$ doesn’t cover all walkable nodes} \end{cases} $$
3. The solution is thus $f(r_{\rm start}, c_{\rm start}, V = \{ (r_{\rm start}, c_{\rm start})\})$.
4. Note that given the input size, we could use a bitset instead of the real set structure to speed up the evaluation of $f$.
5. One could use memoization to further optimize things, but in this case few if any memoized result will be called; thus it does not worth the bang for the buck and not to mention the increased memory foot print..C++ users shall experience MLE when using this technique.

Time Complexity

$O(4^{R \cdot C})$

Code

• Library code omiited. Y combinator structure could be found in http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html

class Solution {
 public:
  int uniquePathsIII(vector<vector<int>>& grid) {

    const auto R{size(grid)}, C{size(grid[0])};
    const array<int, 4> dr{0, 0, -1, 1};
    const array<int, 4> dc{1, -1, 0, 0};

    auto hash_code = [&](int r, int c) { return (r * C + c); };
    auto test_all = [](int state, int r, int c) { return state == ((1 << (r * c)) - 1); };
    auto flip = [&](int state, int r, int c) { return state ^ (1 << hash_code(r, c)); };
    auto test = [&](int state, int r, int c) { return (state & (1 << hash_code(r, c))) > 0; };
    auto within_bound = [&](int r, int c) { return r >= 0 and r < R and c >= 0 and c < C; };

    const auto start_point {[&](array<int, 2> self = {}) {
      for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
          if (grid[r][c] == 1) { self[0] = r; self[1] = c; break; };
      return self;
    }()};

    const auto end_point {[&](array<int, 2> self = {}) {
      for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
          if (grid[r][c] == 2) { self[0] = r; self[1] = c; break; };
      return self;
    }()};

    const auto initial_state {[&] {
      int self = 0;
      for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
          if (grid[r][c] == -1 or grid[r][c] == 1) {
            self |= (1 << hash_code(r, c));
          }
      return self;
    }()};

    auto f = rec([&](auto&& f, int r, int c, int state)  -> int {
      if (r == end_point[0] and c == end_point[1]) {
        return test_all(state, R, C) ? 1 : 0;
      }
      else {
        int acc = 0;
        for (int step = 0; step < 4; ++step) {
          if (const auto [nr, nc] = tuple{r + dr[step], c + dc[step]};
              within_bound(nr, nc) and grid[nr][nc] != -1 and not test(state, nr, nc)) 
            acc += f(nr, nc, flip(state, nr, nc));
        }
        return acc;
      }
    });

    return f(start_point[0], start_point[1], initial_state);
  }
};