不同路径 III

记住「踩格标记 → 四向递归 → 退格还原」，到 E 时剩余待走格为 0 才计一条。下面在官方样例上一步步走。

准备:数清要走的格子：先扫一遍网格：非障碍格共 11 个（这就是必须全部踩到的格子数），起点 S 在 (0,0)，障碍 X 在 (2,3) 不能走。

尝试 · 第 1 步：从起点 S 出发，踩进格子 (0,0)：把它标记为已占用（紫色 = 正踩、黄色 = 路径已占用的格），剩余待走 left 减一。

尝试 · 第 2 步：继续往邻居走，踩进格子 (1,0)：把它标记为已占用（紫色 = 正踩、黄色 = 路径已占用的格），剩余待走 left 减一。

尝试 · 第 3 步：继续往邻居走，踩进格子 (2,0)：把它标记为已占用（紫色 = 正踩、黄色 = 路径已占用的格），剩余待走 left 减一。

尝试 · 第 4 步：继续往邻居走，踩进格子 (2,1)：把它标记为已占用（紫色 = 正踩、黄色 = 路径已占用的格），剩余待走 left 减一。

到 E 了,但是…：这条线很快摸到了终点 E，可是回头一看：还有 6 个空格没踩过！「恰好走遍每个格」没满足，这不是合法路径，要原路退回去换方向。

回溯:撤销刚才的格子：回溯的关键动作：把刚才标记过的格子一个个还原成可走（撤销标记、left 加回去），这样换个方向时这些格子还能被别的路径走到。

路径① · 第 1 步：踩进 (0,0)（紫色），目前已占用 1 个格、还剩 10 个待走。继续朝没走过的邻居探。

路径① · 第 2 步：踩进 (1,0)（紫色），目前已占用 2 个格、还剩 9 个待走。继续朝没走过的邻居探。

路径① · 第 3 步：踩进 (2,0)（紫色），目前已占用 3 个格、还剩 8 个待走。继续朝没走过的邻居探。

路径① · 第 4 步：踩进 (2,1)（紫色），目前已占用 4 个格、还剩 7 个待走。继续朝没走过的邻居探。

路径① · 第 5 步：踩进 (1,1)（紫色），目前已占用 5 个格、还剩 6 个待走。继续朝没走过的邻居探。

路径① · 第 6 步：踩进 (0,1)（紫色），目前已占用 6 个格、还剩 5 个待走。继续朝没走过的邻居探。

路径① · 第 7 步：踩进 (0,2)（紫色），目前已占用 7 个格、还剩 4 个待走。继续朝没走过的邻居探。

路径① · 第 8 步：踩进 (0,3)（紫色），目前已占用 8 个格、还剩 3 个待走。继续朝没走过的邻居探。

路径① · 第 9 步：踩进 (1,3)（紫色），目前已占用 9 个格、还剩 2 个待走。继续朝没走过的邻居探。

路径① · 第 10 步：踩进 (1,2)（紫色），目前已占用 10 个格、还剩 1 个待走。继续朝没走过的邻居探。

合法路径 ① ✔：这一次踩满了全部 11 个空格才到 E，剩余待走恰好为 0，第 1 条合法路径成立，答案计数 +1。绿色就是这条路径。

继续回溯,找下一条：第 1 条记下后并不停手：回溯把网格还原，再从起点换一个出发方向，看还有没有别的走法能踩满全部格子。

路径② · 第 1 步：这条线先沿第一行走：踩进 (0,0)，已占用 1 格、还剩 10 格待走。

路径② · 第 2 步：这条线先沿第一行走：踩进 (0,1)，已占用 2 格、还剩 9 格待走。

路径② · 第 3 步：这条线先沿第一行走：踩进 (0,2)，已占用 3 格、还剩 8 格待走。

路径② · 第 4 步：这条线先沿第一行走：踩进 (0,3)，已占用 4 格、还剩 7 格待走。

路径② · 第 5 步：这条线先沿第一行走：踩进 (1,3)，已占用 5 格、还剩 6 格待走。

路径② · 第 6 步：这条线先沿第一行走：踩进 (1,2)，已占用 6 格、还剩 5 格待走。

路径② · 第 7 步：这条线先沿第一行走：踩进 (1,1)，已占用 7 格、还剩 4 格待走。

路径② · 第 8 步：这条线先沿第一行走：踩进 (1,0)，已占用 8 格、还剩 3 格待走。

路径② · 第 9 步：这条线先沿第一行走：踩进 (2,0)，已占用 9 格、还剩 2 格待走。

路径② · 第 10 步：这条线先沿第一行走：踩进 (2,1)，已占用 10 格、还剩 1 格待走。

合法路径 ② ✔：换的这条线同样踩满全部 11 个空格、剩余为 0，第 2 条合法路径成立，计数再 +1。它和第 1 条经过的顺序不同，是另一条路。

穷举结束 · 答案 = 2：所有方向都试完、再没有新的合法走法。整个过程只有两条路径踩满了全部空格，所以答案是 2。

边界先想清：紧邻终点、必须绕路覆盖、根本覆盖不全（答案 0）。

面试常追问「为什么敢暴力」（看数据范围）和「位掩码记忆化」进阶解。