本题让我们求不相交路径数目
方法1：递归/回溯
dfs(x, y, left) 表示从点x, y出发，还剩下left个可行走点的路径数目。
每行走到一个新的点就将该点设置为-1, 避免重复搜索。
当走到终点时，如果left == 0 则答案 + 1
class Solution { int dfs(vector<vector<int>> &grid, int x, int y, int left) { if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] < 0) { return 0; } if(grid[x][y] == 2) return left == 0; grid[x][y] = -1; int ans = dfs(grid, x - 1, y, left - 1) + dfs(grid, x, y - 1, left - 1) + dfs(grid, x + 1, y, left - 1) + dfs(grid, x, y + 1, left - 1); grid[x][y] = 0; return ans; } public: int uniquePathsIII(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(), sx, sy, cnt = 0; for(int i = 0; i < m; i ++ ) { for(int j = 0; j < n; j ++ ) { if(grid[i][j] == 0) cnt ++ ; else if(grid[i][j] == 1) sx = i, sy = j; } } return dfs(grid, sx, sy, cnt + 1); } };
方法二：位运算和状态压缩
class Solution { public: int uniquePathsIII(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(), vis = 0, sx, sy; for(int i = 0; i < m; i ++ ) { for(int j = 0; j < n; j ++ ) { if(grid[i][j] < 0) vis |= 1 << (i * n + j); else if(grid[i][j] == 1) sx = i, sy = j; } } int all = (1 << m * n) - 1; unordered_map<int, int> memo; function<int(int, int, int)> dfs = [&](int x, int y, int vis) -> int { int p = x * n + y; if(x < 0 || x >= m || y < 0 || y >= n || vis >> p & 1) return 0; vis |= 1 << p; if(grid[x][y] == 2) return vis == all; int key = (p << m * n) | vis; //这里进行哈希，把p和vis拼起来 if(memo.count(key)) return memo[key]; return memo[key] = dfs(x - 1, y, vis) + dfs(x, y - 1, vis) + dfs(x + 1, y, vis) + dfs(x, y + 1, vis); }; return dfs(sx, sy, vis); } };