Leetcode 351 Android 解锁模式

Question

我正在尝试从 Leetcode 解决这个问题。 351. Android Unlock Patterns。但是经过大约5个小时的调试，我找不到这个bug。问题描述如下：

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern:

Each pattern must connect at least m keys and at most n keys.

All the keys must be distinct.

If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.

The order of keys used matters.

Explanation:
| 1 | 2 | 3 |
| 4 | 5 | 6 | 
| 7 | 8 | 9 | 
Invalid move: 4 - 1 - 3 - 6 Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2 Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6 Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2 Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

我使用回溯来解决这个问题，这样我就不能使用太复杂的测试用例进行调试。我的代码可以在 n = m =1 和 n = m = 2 时通过，但在 n = m = 3 时失败。我的代码将输出 304 而不是 320。

我知道锁图案是对称的，即角上的点和边缘中间的点输出相同，所以如果找到一个，我们可以乘以四。最后，处理中心点。对于m = n = 3，我什至尝试画出所有可能的组合，我得到角点有31，中间点有35，中心点有40，所以总组合为31 * 4 + 35 * 4 + 40 = 304。检查重画了好几遍，还是找不到漏掉的16在哪里。

我也查看了这个问题的讨论区的帖子。我觉得这些方法非常相似，但我不知道为什么我会失败。

这是我的代码

class Solution {
    // Every dot can to go. 
    // 1 2 3
    // 4 5 6
    // 7 8 9
    int[][] directions = new int[][] {
        {0},
        {2, 4, 5, 6, 8},
        {1, 3, 4, 5, 6, 7, 9},
        {2, 4, 5, 6, 8},
        {1, 2, 3, 5, 7, 8, 9},
        {1, 2, 3, 4, 6, 7, 8, 9},
        {1, 2, 3, 5, 7, 8, 9},
        {2, 4, 5, 6, 8},
        {1, 3, 4, 5, 6, 7, 9},
        {2, 4, 5, 6, 8}
    };
    int m, n;

    public int numberOfPatterns(int m, int n) {
        this.m = m;
        this.n = n;
        int res = 0;
        boolean[] visited = new boolean[10];
        res += dfs(1, 1, 0, visited) * 4;
        res += dfs(2, 1, 0, visited) * 4;
        res += dfs(5, 1, 0, visited);

        return res;
    }

    public int dfs(int cur, int len, int tempRes, boolean[] visited) {
        if (len > n || visited[cur]) return tempRes;
        if (len >= m && len <= n) tempRes++;
        visited[cur] = true;
        for (Integer child: directions[cur]) {
            tempRes = dfs(child, len + 1, tempRes, visited);
        }
        visited[cur] = false;
        return tempRes;
    }
}

所有的帮助都会很棒，非常感谢。

Answer 1

Valid move: 6 - 5 - 4 - 1 - 9 - 2 Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

您的代码没有考虑到这种可能性。这解释了为什么长度为 3 的模式被 16 略微计数不足：从中间 5 开始，可能有以下模式：

5->1->9、5->2->8、5->3->7 等（总共有 8 个图案从中心移动到每个相邻的方格，然后跳回中心）。

从键 4 开始，有两个模式被跳过：4->1->7 和 4->7->1。这被镜像了 3 次（我们可以从任何一侧的点开始，{2, 4, 6, 8}）。 8 + 8 = 16，占所有缺失的模式。

如果你调整你的逻辑来处理这个问题，你应该回到正轨。

Leetcode 351 Android 解锁模式

Leetcode 351 Android Unlock Patterns

java

algorithm

backtracking