980. 不同路径 III
题目描述
输入一个 m x n 的整数网格 grid，每格取以下四种值之一：1 是起点，2 是终点，0 是可以经过的空格，-1 是不能进入的障碍。起点和终点各恰好有一个，可以在网格的任何位置。
每一步可以向上、下、左、右移动一格。一条合法路径从起点出发、在终点结束，并且要把所有不是障碍的格子（含起点和终点）都恰好走过一次。
返回合法路径的条数。
示例 1
输入：grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]] 输出：2
解释：绕过右下角的障碍，有两种走法能覆盖全部空格。
示例 2
输入：grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]] 输出：4
解释：没有障碍时，共有 4 种走法覆盖全部格子。
示例 3
输入：grid = [[0,1],[2,0]] 输出：0
解释：无论怎么走都无法把每个空格各走一次后停在终点。
数据范围
1 <= grid.length * grid[0].length <= 20
解题思路：回溯搜索
先统计非障碍格的数量 need（包括起点和终点），并找到起点。dfs(r, c, left) 表示站在 (r, c)、还有 left 个格子（含当前格）没走。到达终点时，只有 left == 1（只剩终点自己）才算一条合法路径。否则把当前格标为 -1 防止重走，向四个方向递归，返回前恢复为 0。
为什么正确
进入 dfs(r, c, left) 时，已经走过的格子都被标成 -1，且 left = need - 已走过的格子数。
复杂度分析
时间 O(3^(mn))（每格最多 3 个新方向），空间 O(mn) 的递归栈。
易错点
need 要把起点和终点都算上；到终点但还有空格没走时要返回 0，不能继续从终点往外走；回溯时一定要恢复格子。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
need = 0
for i in range(m):
for j in range(n):
if grid[i][j] != -1:
need += 1
if grid[i][j] == 1:
si, sj = i, j
def dfs(r, c, left):
if grid[r][c] == 2:
return 1 if left == 1 else 0
grid[r][c] = -1
total = 0
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != -1:
total += dfs(nr, nc, left - 1)
grid[r][c] = 0
return total
return dfs(si, sj, need)class Solution {
int[][] grid;
int m, n;
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
public int uniquePathsIII(int[][] grid) {
this.grid = grid;
m = grid.length; n = grid[0].length;
int need = 0, si = 0, sj = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] != -1)
need++;
if (grid[i][j] == 1) {
si = i;
sj = j;
}
}
return dfs(si, sj, need);
}
int dfs(int r, int c, int left) {
if (grid[r][c] == 2)
return left == 1 ? 1 : 0;
grid[r][c] = -1;
int total = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != -1)
total += dfs(nr, nc, left - 1);
}
grid[r][c] = 0;
return total;
}
}class Solution {
public:
int uniquePathsIII(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int need = 0, si = 0, sj = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] != -1)
need++;
if (grid[i][j] == 1) {
si = i;
sj = j;
}
}
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
function<int(int, int, int)> dfs = [&](int r, int c, int left) -> int {
if (grid[r][c] == 2)
return left == 1 ? 1 : 0;
grid[r][c] = -1;
int total = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != -1)
total += dfs(nr, nc, left - 1);
}
grid[r][c] = 0;
return total;
};
return dfs(si, sj, need);
}
};func uniquePathsIII(grid [][]int) int {
m, n := len(grid), len(grid[0])
need, si, sj := 0, 0, 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] != -1 {
need++
}
if grid[i][j] == 1 {
si, sj = i, j
}
}
}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var dfs func(r, c, left int) int
dfs = func(r, c, left int) int {
if grid[r][c] == 2 {
if left == 1 {
return 1
}
return 0
}
grid[r][c] = -1
total := 0
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != -1 {
total += dfs(nr, nc, left-1)
}
}
grid[r][c] = 0
return total
}
return dfs(si, sj, need)
}var uniquePathsIII = function(grid) {
const m = grid.length, n = grid[0].length;
let need = 0, si = 0, sj = 0;
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++) {
if (grid[i][j] !== -1)
need++;
if (grid[i][j] === 1) {
si = i;
sj = j;
}
}
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const dfs = (r, c, left) => {
if (grid[r][c] === 2)
return left === 1 ? 1 : 0;
grid[r][c] = -1;
let total = 0;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] !== -1)
total += dfs(nr, nc, left - 1);
}
grid[r][c] = 0;
return total;
};
return dfs(si, sj, need);
};function uniquePathsIII(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
let need = 0, si = 0, sj = 0;
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++) {
if (grid[i][j] !== -1)
need++;
if (grid[i][j] === 1) {
si = i;
sj = j;
}
}
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const dfs = (r: number, c: number, left: number): number => {
if (grid[r][c] === 2)
return left === 1 ? 1 : 0;
grid[r][c] = -1;
let total = 0;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] !== -1)
total += dfs(nr, nc, left - 1);
}
grid[r][c] = 0;
return total;
};
return dfs(si, sj, need);
}其他解法
回溯直接枚举所有路径，代码简单，空间只需递归栈；状态压缩记忆化合并了重复状态，是“哈密顿路径计数”的通用做法，但需要额外的哈希表。
解法 2：状态压缩记忆化搜索 时间 O(mn · 2^(mn))，空间 O(mn · 2^(mn))
把格子编号为 r·n + c，用一个二进制数 mask 记录已经走过的格子。状态 (cell, mask) 表示当前站在 cell、已访问集合为 mask 时，走到终点的路径数。到达终点时，只有 mask 等于所有非障碍格的集合才算一条路径。转移时枚举四个方向上没访问过的格子，结果用哈希表记忆化，相同状态只计算一次。
当不同路线到达相同的位置和访问集合时可以复用结果，体现了状态压缩 DP 的思想。状态数理论上很大，本题格子不超过 20 个才可行，而且实际运行不一定比剪枝良好的回溯快。
from functools import lru_cache
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
full = 0
for i in range(m):
for j in range(n):
if grid[i][j] != -1:
full |= 1 << (i * n + j)
if grid[i][j] == 1:
start = i * n + j
@lru_cache(maxsize=None)
def dp(cell, mask):
r, c = divmod(cell, n)
if grid[r][c] == 2:
return 1 if mask == full else 0
total = 0
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != -1:
nxt = nr * n + nc
if not mask >> nxt & 1:
total += dp(nxt, mask | 1 << nxt)
return total
return dp(start, 1 << start)class Solution {
int m, n, full;
int[][] grid;
Map<Long, Integer> memo = new HashMap<>();
int dp(int cell, int mask) {
int r = cell / n, c = cell % n;
if (grid[r][c] == 2) return mask == full ? 1 : 0;
long key = (long) mask * 32 + cell;
Integer got = memo.get(key);
if (got != null) return got;
int total = 0;
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] == -1) continue;
int nxt = nr * n + nc;
if ((mask >> nxt & 1) != 0) continue;
total += dp(nxt, mask | 1 << nxt);
}
memo.put(key, total);
return total;
}
public int uniquePathsIII(int[][] g) {
grid = g;
m = grid.length;
n = grid[0].length;
full = 0;
memo.clear();
int start = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != -1) full |= 1 << (i * n + j);
if (grid[i][j] == 1) start = i * n + j;
}
}
return dp(start, 1 << start);
}
}class Solution {
public:
int m, n, full;
vector<vector<int>> grid;
unordered_map<long long, int> memo;
int dp(int cell, int mask) {
int r = cell / n, c = cell % n;
if (grid[r][c] == 2) return mask == full ? 1 : 0;
long long key = (long long) mask * 32 + cell;
auto it = memo.find(key);
if (it != memo.end()) return it->second;
int total = 0;
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] == -1) continue;
int nxt = nr * n + nc;
if (mask >> nxt & 1) continue;
total += dp(nxt, mask | 1 << nxt);
}
memo[key] = total;
return total;
}
int uniquePathsIII(vector<vector<int>>& g) {
grid = g;
m = grid.size();
n = grid[0].size();
full = 0;
int start = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != -1) full |= 1 << (i * n + j);
if (grid[i][j] == 1) start = i * n + j;
}
}
return dp(start, 1 << start);
}
};func uniquePathsIII(grid [][]int) int {
m, n := len(grid), len(grid[0])
full, start := 0, 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] != -1 {
full |= 1 << (i*n + j)
}
if grid[i][j] == 1 {
start = i*n + j
}
}
}
memo := map[int]int{}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var dp func(cell, mask int) int
dp = func(cell, mask int) int {
r, c := cell/n, cell%n
if grid[r][c] == 2 {
if mask == full {
return 1
}
return 0
}
key := mask*32 + cell
if v, ok := memo[key]; ok {
return v
}
total := 0
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] == -1 {
continue
}
nxt := nr*n + nc
if mask>>nxt&1 == 1 {
continue
}
total += dp(nxt, mask|1<<nxt)
}
memo[key] = total
return total
}
return dp(start, 1<<start)
}var uniquePathsIII = function(grid) {
const m = grid.length, n = grid[0].length;
let full = 0, start = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] !== -1) full |= 1 << (i * n + j);
if (grid[i][j] === 1) start = i * n + j;
}
}
const memo = new Map();
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const dp = (cell, mask) => {
const r = Math.floor(cell / n), c = cell % n;
if (grid[r][c] === 2) return mask === full ? 1 : 0;
const key = mask * 32 + cell;
if (memo.has(key)) return memo.get(key);
let total = 0;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] === -1) continue;
const nxt = nr * n + nc;
if (mask >> nxt & 1) continue;
total += dp(nxt, mask | 1 << nxt);
}
memo.set(key, total);
return total;
};
return dp(start, 1 << start);
};function uniquePathsIII(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
let full = 0, start = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] !== -1) full |= 1 << (i * n + j);
if (grid[i][j] === 1) start = i * n + j;
}
}
const memo = new Map<number, number>();
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const dp = (cell: number, mask: number): number => {
const r = Math.floor(cell / n), c = cell % n;
if (grid[r][c] === 2) return mask === full ? 1 : 0;
const key = mask * 32 + cell;
const got = memo.get(key);
if (got !== undefined) return got;
let total = 0;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] === -1) continue;
const nxt = nr * n + nc;
if (mask >> nxt & 1) continue;
total += dp(nxt, mask | 1 << nxt);
}
memo.set(key, total);
return total;
};
return dp(start, 1 << start);
}