跳转至

LeetCode: 351. 安卓系统手势解锁

1、题目描述

我们都知道安卓有个手势解锁的界面,是一个 3 x 3 的点所绘制出来的网格。

给你两个整数,分别为 mn,其中 1 ≤ m ≤ n ≤ 9,那么请你统计一下有多少种解锁手势,是至少需要经过 m 个点,但是最多经过不超过 n 个点的。

先来了解下什么是一个有效的安卓解锁手势:

  • 每一个解锁手势必须至少经过 m 个点、最多经过 n 个点。
  • 解锁手势里不能设置经过重复的点。
  • 假如手势中有两个点是顺序经过的,那么这两个点的手势轨迹之间是绝对不能跨过任何未被经过的点。
  • 经过点的顺序不同则表示为不同的解锁手势。

img

解释:

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |

无效手势:4 - 1 - 3 - 6 连接点 1 和点 3 时经过了未被连接过的 2 号点。

无效手势:4 - 1 - 9 - 2 连接点 1 和点 9 时经过了未被连接过的 5 号点。

有效手势:2 - 4 - 1 - 3 - 6 连接点 1 和点 3 是有效的,因为虽然它经过了点 2 ,但是点 2 在该手势中之前已经被连过了。

有效手势:6 - 5 - 4 - 1 - 9 - 2 连接点 1 和点 9 是有效的,因为虽然它经过了按键 5 ,但是点 5 在该手势中之前已经被连过了。

示例:

输入: m = 1,n = 1
输出: 9

2、解题思路

  • 带状态的深度优先搜索 首先明确一下能够直达的位置:
  • 水平
  • 垂直
  • 对角线
  • 日子型(例如象棋中的马,数字1可以直接到6,8)

因此,我们将当前数字不能到到的位置统计出来,如果想要到达,就必须经过某个点

例如,
1 -> 3,经过2
1 -> 7,经过4
2 -> 8,经过5

我们将这些位置进行标记
graph = {
    1: {3: 2, 7: 4, 9: 5},
    2: {8: 5},
    3: {1: 2, 7: 5, 9: 6},
    4: {6: 5},
    5: {},
    6: {4: 5},
    7: {1: 4, 3: 5, 9: 8},
    8: {2: 5},
    9: {1: 5, 3: 6, 7: 8},
}
由于数字很少,我们采用位标记当前是否走过,基本思路为: - 判断当前走过的路径是否到了n步,到了则返回1 - 判断当前步伐是否大于等于m,是的话,ans加一 - 判断当前节点能够经过的所有未走过的节点 - 如果能够直达,更新状态,递归 - 如果不能直达,根据上面的到达条件判断,是否已经经过必经路线

优化: 由于从1,3,7,9出发的线路是同样的数量,从2,4,6,8也是,因此

ans += 4 * dfs(1 << 1, 1, 1)
ans += 4 * dfs(1 << 2, 2, 1)
ans += dfs(1 << 5, 5, 1)
仅需要计算上面3个点出发的即可得到结果

from functools import lru_cache


class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        graph = {
            1: {3: 2, 7: 4, 9: 5},
            2: {8: 5},
            3: {1: 2, 7: 5, 9: 6},
            4: {6: 5},
            5: {},
            6: {4: 5},
            7: {1: 4, 3: 5, 9: 8},
            8: {2: 5},
            9: {1: 5, 3: 6, 7: 8},
        }
        ans = 0

        @lru_cache(None)
        def dfs(status, current, count):
            if count == n:
                return 1
            current_ans = 0 if count < m else 1
            for i in range(1, 10):
                if status & (1 << i) == 0:
                    if i not in graph[current] or ((1 << graph[current][i]) & status):
                        current_ans += dfs(status | (1 << i), i, count + 1)
            return current_ans

        # for cur in range(1, 10):
            # ans += dfs(1 << cur, cur, 1)

        ans += 4 * dfs(1 << 1, 1, 1)
        ans += 4 * dfs(1 << 2, 2, 1)
        ans += dfs(1 << 5, 5, 1)

        return ans