Backtrack by using bit mask to record visited nodes

LC 980. Unique Paths III

Photo by Anne Nygård on Unsplash

About using Bit mask as visited or seen in BFS/DFS

For BFS/DFS problems, we usually need to maintain a seen or visited variable to make sure that we do not visit the visited node again (to get rid of TLE). Usually, we can use a set(unorder set in c++ and set in python) or array to maintain the visited status. Sometimes, when the nodes number is limited, such as less than 32, we can use bit mask. One bit is one node. Set to 1 means visited and 0 means not visited.

About backtrack

When we want to find all feasible solutions instead of one solution, we should explore all possibilities. For this case, we need to use backtrack instead of simple BFS or DFS. The trick is when we find one path, we keep on exploring instead of stopping.

Backtrack with pruning

Backtrack has an exponential complexity, luckily, we can prune branches if it is not feasible. For example, in the problem introduced in this article, lots of branches are infeasible, so the backtracking can be executed fast.

Problem

980. Unique Paths III

Reference Code

using PII = pair<int, int>;
vector<PII> dirs = {{0, 1},{0, -1},{1, 0},{-1, 0}};
class Solution {
public:
    void backtrack(int n, int m, int status, int start, int end, int steps, int target_step, int &ret){
        if (status & (1 << start))return;
        status |= (1<<start);
        steps++;
        if (start == end){
            if (steps == target_step) ret++;
            return;
        }
        int i = start/m, j = start%m;
        for (auto [di, dj]: dirs){
            int r = i + di, c = j + dj;
            int new_start = r*m + c;
            if (r < 0 || r >= n || c < 0 || c >= m || status & (1 << new_start))continue;
            backtrack(n, m, status, new_start , end, steps  , target_step, ret);
        }
        return;
        
    }
    int uniquePathsIII(vector<vector<int>>& grid) {
        const int n = grid.size(), m = grid[0].size();
        int target_steps = n*m, start = 0, end = 0, status=0;
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                if (grid[i][j] == -1){
                    status |= (1 << (i*m+j));
                    target_steps--;
                }
                else if (grid[i][j] == 2){
                    end = i*m + j;
                } else if (grid[i][j] == 1){
                    start = i*m + j;
                }
            }
        }
        int ret = 0;
        backtrack(n, m, status, start , end, 0, target_steps, ret);
        return ret;
        
        
    }
};

run time

Runtime: 0 ms

Tricks used

The trick we used here:

• bit mask to maintain the status. When we visit a node, set it as 1

status |= (1<<start);

• for the obstacles, we also set it as 1, so it will not be visited again.
• Change the location (i, j) to I*m + j where m is the number of elements in one row.

Time complexity

As each node (except the first one) has at most 3 neighbors to explore, the complexity is O(3^(n*m)). For this problem, n*m ≤ 20, we have

3^20 = 3,486,784,401

As lots of branches can be pruned, the runtime is 0ms for C++.

Thanks for reading, more of my articles on different topics can be found here.