不同路径 III 图解题解

这道题到底在问什么

输入

[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

输出

2（两条路覆盖全部 11 个空格）

最优解：一步一步想明白

1. 3记住「踩格标记 → 四向递归 → 退格还原」，到 E 时剩余待走格为 0 才计一条。下面在官方样例上一步步走。
2. 4先扫一遍网格：非障碍格共 11 个（这就是必须全部踩到的格子数），起点 S 在 (0,0)，障碍 X 在 (2,3) 不能走。
3. 5从起点 S 出发，踩进格子 (0,0)：把它标记为已占用（紫色 = 正踩、黄色 = 路径已占用的格），剩余待走 left 减一。
4. 6继续往邻居走，踩进格子 (1,0)：把它标记为已占用（紫色 = 正踩、黄色 = 路径已占用的格），剩余待走 left 减一。
5. 7继续往邻居走，踩进格子 (2,0)：把它标记为已占用（紫色 = 正踩、黄色 = 路径已占用的格），剩余待走 left 减一。
6. 8继续往邻居走，踩进格子 (2,1)：把它标记为已占用（紫色 = 正踩、黄色 = 路径已占用的格），剩余待走 left 减一。
7. 9这条线很快摸到了终点 E，可是回头一看：还有 6 个空格没踩过！「恰好走遍每个格」没满足，这不是合法路径，要原路退回去换方向。
8. 10回溯的关键动作：把刚才标记过的格子一个个还原成可走（撤销标记、left 加回去），这样换个方向时这些格子还能被别的路径走到。
9. 11踩进 (0,0)（紫色），目前已占用 1 个格、还剩 10 个待走。继续朝没走过的邻居探。
10. 12踩进 (1,0)（紫色），目前已占用 2 个格、还剩 9 个待走。继续朝没走过的邻居探。
11. 13踩进 (2,0)（紫色），目前已占用 3 个格、还剩 8 个待走。继续朝没走过的邻居探。
12. 14踩进 (2,1)（紫色），目前已占用 4 个格、还剩 7 个待走。继续朝没走过的邻居探。
13. 15踩进 (1,1)（紫色），目前已占用 5 个格、还剩 6 个待走。继续朝没走过的邻居探。
14. 16踩进 (0,1)（紫色），目前已占用 6 个格、还剩 5 个待走。继续朝没走过的邻居探。
15. 17踩进 (0,2)（紫色），目前已占用 7 个格、还剩 4 个待走。继续朝没走过的邻居探。
16. 18踩进 (0,3)（紫色），目前已占用 8 个格、还剩 3 个待走。继续朝没走过的邻居探。
17. 19踩进 (1,3)（紫色），目前已占用 9 个格、还剩 2 个待走。继续朝没走过的邻居探。
18. 20踩进 (1,2)（紫色），目前已占用 10 个格、还剩 1 个待走。继续朝没走过的邻居探。
19. 21这一次踩满了全部 11 个空格才到 E，剩余待走恰好为 0，第 1 条合法路径成立，答案计数 +1。绿色就是这条路径。
20. 22第 1 条记下后并不停手：回溯把网格还原，再从起点换一个出发方向，看还有没有别的走法能踩满全部格子。
21. 23这条线先沿第一行走：踩进 (0,0)，已占用 1 格、还剩 10 格待走。
22. 24这条线先沿第一行走：踩进 (0,1)，已占用 2 格、还剩 9 格待走。
23. 25这条线先沿第一行走：踩进 (0,2)，已占用 3 格、还剩 8 格待走。
24. 26这条线先沿第一行走：踩进 (0,3)，已占用 4 格、还剩 7 格待走。
25. 27这条线先沿第一行走：踩进 (1,3)，已占用 5 格、还剩 6 格待走。
26. 28这条线先沿第一行走：踩进 (1,2)，已占用 6 格、还剩 5 格待走。
27. 29这条线先沿第一行走：踩进 (1,1)，已占用 7 格、还剩 4 格待走。
28. 30这条线先沿第一行走：踩进 (1,0)，已占用 8 格、还剩 3 格待走。
29. 31这条线先沿第一行走：踩进 (2,0)，已占用 9 格、还剩 2 格待走。
30. 32这条线先沿第一行走：踩进 (2,1)，已占用 10 格、还剩 1 格待走。
31. 33换的这条线同样踩满全部 11 个空格、剩余为 0，第 2 条合法路径成立，计数再 +1。它和第 1 条经过的顺序不同，是另一条路。
32. 34所有方向都试完、再没有新的合法走法。整个过程只有两条路径踩满了全部空格，所以答案是 2。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        todo = 0
        sr = sc = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] != -1:
                    todo += 1
                if grid[r][c] == 1:
                    sr, sc = r, c
        def dfs(r, c, left):
            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == -1:
                return 0
            if grid[r][c] == 2:
                return 1 if left == 1 else 0
            tmp = grid[r][c]
            grid[r][c] = -1
            ans = dfs(r+1,c,left-1) + dfs(r-1,c,left-1) + dfs(r,c+1,left-1) + dfs(r,c-1,left-1)
            grid[r][c] = tmp
            return ans
        return dfs(sr, sc, todo)

#include <vector>
using namespace std;
class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), todo = 0, sr = 0, sc = 0;
        for (int r = 0; r < m; ++r) for (int c = 0; c < n; ++c) {
            if (grid[r][c] != -1) todo++;
            if (grid[r][c] == 1) { sr = r; sc = c; }
        }
        function<int(int,int,int)> dfs = [&](int r, int c, int left) {
            if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == -1) return 0;
            if (grid[r][c] == 2) return left == 1 ? 1 : 0;
            int old = grid[r][c];
            grid[r][c] = -1;
            int ans = dfs(r+1,c,left-1) + dfs(r-1,c,left-1) + dfs(r,c+1,left-1) + dfs(r,c-1,left-1);
            grid[r][c] = old;
            return ans;
        };
        return dfs(sr, sc, todo);
    }
};

import java.util.*;
class Solution {
    int[][] grid; int m, n;
    public int uniquePathsIII(int[][] grid) {
        this.grid = grid; m = grid.length; n = grid[0].length;
        int todo = 0, sr = 0, sc = 0;
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
            if (grid[r][c] != -1) todo++;
            if (grid[r][c] == 1) { sr = r; sc = c; }
        }
        return dfs(sr, sc, todo);
    }
    private int dfs(int r, int c, int left) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == -1) return 0;
        if (grid[r][c] == 2) return left == 1 ? 1 : 0;
        int old = grid[r][c]; grid[r][c] = -1;
        int ans = dfs(r+1,c,left-1) + dfs(r-1,c,left-1) + dfs(r,c+1,left-1) + dfs(r,c-1,left-1);
        grid[r][c] = old;
        return ans;
    }
}

复杂度

面试官可能追问