android-unlock-patterns.cpp

// Time:  O(9 * 2^9)
// Space: O(9 * 2^9)

// DP solution.
class Solution {
public:
    int numberOfPatterns(int m, int n) {
        // dp[i][j]: i is the set of the numbers in binary presentation,
        //           d[i][j] is the number of ways ending with the number j.
        vector<vector<int>> dp(1 << 9 , vector<int>(9, 0));
        for (int i = 0; i < 9; ++i) {
            dp[merge(0, i)][i] = 1;
        }

        vector<int> keys(9, 0);
        for (int used = 0; used < dp.size(); ++used) {
            const auto number = number_of_key(used);
            if (number > n) {
                continue;
            }
            for (int i = 0; i < 9; ++i) {
                if (!contain(used, i)) {
                    continue;
                }
                keys[number - 1] += dp[used][i];

                const auto x1 = i / 3;
                const auto y1 = i % 3;
                for (int j = 0; j < 9; ++j) {
                    if (contain(used, j)) {
                        continue;
                    }
                    const auto x2 = j / 3;
                    const auto y2 = j % 3;
                    if (((x1 == x2 && abs(y1 - y2) == 2) ||
                         (y1 == y2 && abs(x1 - x2) == 2) ||
                         (abs(x1 - x2) == 2 && abs(y1 - y2) == 2)) &&
                         !(contain(used, convert((x1 + x2) / 2, (y1 + y2) / 2)))) {
                             continue;
                    }
                    dp[merge(used, j)][j] += dp[used][i];
                }
            }
        }
        int res = 0;
        for (int i = m - 1; i < n; ++i) {
            res += keys[i];
        }
        return res;
    }

private:
    inline int merge(int i, int j) {
        return i | (1 << j);
    }

    inline int number_of_key(int i) {
        int number = 0;
        for (; i; i &= i - 1) {
            ++number;
        }
        return number;
    }

    inline bool contain(int i, int j) {
        return i & (1 << j);
    }

    inline int convert(int i, int j) {
        return 3 * i + j;
    }
};


// Time:  O(9!)
// Space: O(9)
// Backtracking solution.
class Solution2 {
public:
    int numberOfPatterns(int m, int n) {
        int number = 0;
        bool visited[9] = {false};
        // 1, 3, 7, 9
        numberOfPatternsHelper(m, n, 0, 0, 1, visited, &number);
        // 2, 4, 6, 8
        numberOfPatternsHelper(m, n, 0, 1, 1, visited, &number);
        number *= 4;
        // 5
        numberOfPatternsHelper(m, n, 1, 1, 1, visited, &number);
        return number;
    }

private:
    const vector<vector<int>> directions = {
        {1, 0}, {-1, 0}, {0, 1}, {0, -1},
        {1, 1}, {-1, -1}, {1, -1}, {-1, 1},
        {2, 1}, {2, -1}, {-2, -1}, {-2, 1},
        {1, 2}, {-1, 2}, {1, -2}, {-1, -2}
    };

    void numberOfPatternsHelper(int m, int n, int i, int j, int level,
                                bool visited[], int *number) {
        if (level > n) {
            return;
        }

        if (level >= m) {
            ++(*number);
        }

        visited[convert(i, j)] = true;

        for (const auto& direction : directions) {
            auto x = i + direction[0];
            auto y = j + direction[1];
            if (valid(x, y)) {
                if (!visited[convert(x, y)]) {
                    numberOfPatternsHelper(m, n, x, y, level + 1, visited, number);
                } else {
                    x += direction[0];
                    y += direction[1];
                    if (valid(x, y) && !visited[convert(x, y)]) {
                        numberOfPatternsHelper(m, n, x, y, level + 1, visited, number);
                    }
                }
            }
        }

        visited[convert(i, j)] = false;
    }

    inline int convert(int i, int j) {
        return 3 * i + j;
    }

    inline bool valid(int i, int j) {
        return i >= 0 && i < 3 && j >= 0 && j < 3;
    }
};