LeetCode 351. 安卓系统手势解锁
题目描述
题意分析
将九宫格按从上到下、每行从左到右编号为
1..9，统计使用点数在[m, n]内的解锁路径。点不能重复选择；若两个连续选择的点之间经过另一个格点，该中间点必须在此前已经使用。选择顺序不同就是不同手势。
解法：回溯 + 跳跃约束表
核心思路
[!blue]
一条路径能否继续，取决于当前终点和已经使用的点，适合回溯枚举。用
skip[cur][next]保存连线必须经过的中间点，为 0 表示不需要中间点。只有同一行、同一列的两端以及两条长对角线需要跨点，共八对连接；约束与方向无关，所以表中两个方向都要登记。
dfs(cur, remain)表示已经选定当前点cur，还需要再选remain个点时的合法延伸数量。进入函数时，used只标记当前点之前的路径。若remain = 0，这一条目标长度的路径已经完成，返回 1，无需再修改访问状态。否则先标记
cur，枚举每个尚未使用的next。只有不需要中间点，或所需中间点已经在used中，才允许递归。条件恰好对应题目的两条限制，因此不会接出非法路径；每个合法下一点又都会被尝试，因此不会漏解。返回之前取消当前标记，让兄弟分支使用各自的访问集合。对每个目标长度单独计数，起点已占一个位置，所以传入
length - 1。九宫格旋转能把四个角互相映射，也能把四个边中点互相映射，并且保持跨点约束，因此只需分别从角点 1、边中点 2、中心点 5 搜索，再乘以4、4、1。这是用对称性省略等量搜索，旋转后的不同起点手势仍分别计入答案。
解题步骤
- 创建跨点表
skip，登记八对双向约束，并初始化空的used。- 枚举每个目标长度，分别从 1、2、5 出发，递归计数剩余
length - 1个点。- 剩余长度为 0 时返回 1；否则标记当前点，递归尝试所有合法且未使用的下一点。
- 返回前恢复当前点标记，将三个起点的计数按对称数量加权后累加。
代码实现
class Solution {
public int numberOfPatterns(int m, int n) {
int[][] skip = buildSkip();
boolean[] used = new boolean[10];
int total = 0;
for (int len = m; len <= n; len++) {
// 起点已占一项，四角与四边中点分别各有四个对称起点
total += 4 * dfs(1, len - 1, used, skip);
total += 4 * dfs(2, len - 1, used, skip);
total += dfs(5, len - 1, used, skip);
}
return total;
}
private int dfs(int cur, int remain, boolean[] used, int[][] skip) {
if (remain == 0) {
return 1;
}
// 进入时只标记祖先；本层开始扩展才标记当前点
used[cur] = true;
int res = 0;
for (int next = 1; next <= 9; next++) {
int mid = skip[cur][next];
if (!used[next] && (mid == 0 || used[mid])) {
res += dfs(next, remain - 1, used, skip);
}
}
// 恢复当前路径标记，不能影响后续分支
used[cur] = false;
return res;
}
private int[][] buildSkip() {
int[][] skip = new int[10][10];
// 需要跨点的连接要双向登记
skip[1][3] = 2;
skip[3][1] = 2;
skip[1][7] = 4;
skip[7][1] = 4;
skip[3][9] = 6;
skip[9][3] = 6;
skip[7][9] = 8;
skip[9][7] = 8;
skip[1][9] = 5;
skip[9][1] = 5;
skip[3][7] = 5;
skip[7][3] = 5;
skip[2][8] = 5;
skip[8][2] = 5;
skip[4][6] = 5;
skip[6][4] = 5;
return skip;
}
}
func numberOfPatterns(m int, n int) int {
skip := buildSkip()
used := make([]bool, 10)
total := 0
for length := m; length <= n; length++ {
// 起点已占一项，四角与四边中点分别各有四个对称起点
total += 4 * dfsPattern(1, length-1, used, skip)
total += 4 * dfsPattern(2, length-1, used, skip)
total += dfsPattern(5, length-1, used, skip)
}
return total
}
func dfsPattern(cur int, remain int, used []bool, skip [][]int) int {
if remain == 0 {
return 1
}
// 进入时只标记祖先；本层开始扩展才标记当前点
used[cur] = true
res := 0
for next := 1; next <= 9; next++ {
mid := skip[cur][next]
if !used[next] && (mid == 0 || used[mid]) {
res += dfsPattern(next, remain-1, used, skip)
}
}
// 恢复当前路径标记，不能影响后续分支
used[cur] = false
return res
}
func buildSkip() [][]int {
skip := make([][]int, 10)
for i := range skip {
skip[i] = make([]int, 10)
}
// 需要跨点的连接要双向登记
skip[1][3] = 2
skip[3][1] = 2
skip[1][7] = 4
skip[7][1] = 4
skip[3][9] = 6
skip[9][3] = 6
skip[7][9] = 8
skip[9][7] = 8
skip[1][9] = 5
skip[9][1] = 5
skip[3][7] = 5
skip[7][3] = 5
skip[2][8] = 5
skip[8][2] = 5
skip[4][6] = 5
skip[6][4] = 5
return skip
}
复杂度分析
- 时间复杂度：排列前缀搜索量可记为 $O(9!)$ 量级；九个点固定，实际为常数规模。
- 空间复杂度：$O(1)$，固定表与最多九层递归。
关键点总结
[!green]
- 对称性只减少重复搜索，不把不同起点的手势当成同一个答案。
- 终止层不再扩展，无需标记当前点。
- 长度只由新选择的点增加；经过一个已使用的中间点，不会再次增加路径长度。
易错点总结
[!yellow]
- 跨点表漏写反向，会错误放行某方向。
- 把有中点一律禁掉，漏掉中点此前已用的合法路径。
- 标记后提前返回却不恢复，会污染其他分支。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 79. 单词搜索 | 中等 | 同样回溯一条不能重复使用节点的路径，本题某条连线能否使用还取决于中间点是否已访问。 |
| 980. 不同路径 III | 困难 | 同样在访问集合约束下枚举路径，原题要求访问全部格子，本题按长度范围计数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！