Android Unlock Patterns - Đếm mẫu mở khóa Android hợp lệ

Màn hình khóa Android 3x3 (9 điểm). Cho m, n (1 ≤ m ≤ n ≤ 9). Đếm số mẫu mở khóa dùng từ m đến n điểm. Quy tắc: không được nhảy qua điểm chưa chọn (trừ khi điểm giữa đã được chọn). Thứ tự quan trọng.

Ví dụ: m=1, n=1 → 9 mẫu (chọn 1 trong 9 điểm).

Giải thuật (DFS + Backtracking với mảng bỏ qua)

Tiền xử lý mảng skip[i][j] = điểm giữa của i và j (0 nếu không có). DFS từ mỗi điểm bắt đầu, độ dài từ m đến n. Tối ưu: đối xứng góc (1,3,7,9), cạnh (2,4,6,8), trung tâm (5).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int skip[10][10];

    int dfs(int node, int len, vector<bool>& visited) {
        if (len == 0) return 1;
        visited[node] = true;
        int ret = 0;
        for (int i = 1; i <= 9; i++) {
            if (!visited[i] && (skip[node][i] == 0 || visited[skip[node][i]]))
                ret += dfs(i, len - 1, visited);
        }
        visited[node] = false;
        return ret;
    }

    int numberOfPatterns(int m, int n) {
        memset(skip, 0, sizeof(skip));
        skip[1][3] = skip[3][1] = 2;
        skip[1][7] = skip[7][1] = 4;
        skip[3][9] = skip[9][3] = 6;
        skip[7][9] = skip[9][7] = 8;
        skip[4][6] = skip[6][4] = skip[2][8] = skip[8][2] = 
        skip[3][7] = skip[7][3] = skip[1][9] = skip[9][1] = 5;

        vector<bool> visited(10, false);
        int ret = 0;
        for (int i = m; i <= n; i++) {
            ret += dfs(1, i - 1, visited) * 4; // góc
            ret += dfs(2, i - 1, visited) * 4; // cạnh
            ret += dfs(5, i - 1, visited);     // tâm
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.numberOfPatterns(1, 1);
    return 0;
}

Đầu vào

1, 1

Đầu ra

9