java - 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:

1. Each pattern must connect at least m keys and at most n keys.
2. All the keys must be distinct.
3. 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.
4. 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，占所有缺失的模式。

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