Android手机9宫格手势数量:787728 (16格，计算超时)

unlock1.cc

#include <memory>
#include <cassert>

/*
 * @author snk
 *
 * 9 points: 787728
 * 16 points: timeout
 */

const int MAXN = 6;
const char WALL = '*';
const char SPACE = 's';
const char FILL = 'f';
int mp[MAXN][MAXN];

void initMap(int m[][MAXN], int n);
void printMap(int m[][MAXN]);
int dfs(int x, int y, int steps, int n);
void calc(int n);

int main() {
    calc(3); // 9 points
    calc(4); // 16 points
    return 0;
}

void calc(int n) {
    assert(n < MAXN);
    initMap(mp, n);
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            sum += dfs(i, j, 0, n);
        }
    }
    printf("for %d points, total num is: %d\n", n * n, sum);
//    printMap(map);
}

int dfs(int x, int y, int steps, int n) {
    int ret = 0;
    if (mp[x][y] == SPACE) {
        ++steps;
        mp[x][y] = FILL;
        if (steps >= 4) {
            ret += 1;
        }
        // choose next point
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (mp[i][j] == SPACE) { // (x, y) 到 (i, j) 是否可达
                    if ((abs(i - x) <= 1 && abs(j - y) <= 1) ||
                         abs(i - x) != abs(j - y)) {
                        ret += dfs(i, j, steps, n);
                    } else if (abs(i - x) == abs(j - y)) {
                        int vx = i - x > 0 ? 1 : -1;
                        int vy = j - y > 0 ? 1 : -1;
                        if (mp[i - vx][j - vy] == FILL) {
                            ret += dfs(i, j, steps, n);
                        }
                    }
                }
            }
        }
        mp[x][y] = SPACE;
    }
    return ret;
}

void printMap(int m[][MAXN]) {
    for (int i = 0; i < MAXN; ++i) {
        for (int j = 0; j < MAXN; ++j) {
            printf("%c ", m[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void initMap(int m[][MAXN], int n) {
    assert(n < MAXN);
    memset(mp, WALL, sizeof mp);
    printf("\ngenerate a %d points map\n", n * n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            m[i][j] = SPACE;
        }
    }
    printMap(mp);
}

unlock2.cc

#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 3, M = N * N, L = 4;
int use[M] = {0}, a[M];
long long cnt = 0;

int rc2x(int r, int c) {
    return r * N + c;
}

void x2rc(int x, int &r, int &c) {
    r = x / N;
    c = x % N;
}

bool check(int x, int y) {
    int rx, ry, cx, cy;
    x2rc(x, rx, cx);
    x2rc(y, ry, cy);
    if (rx > ry) swap(rx, ry);
    if (cx > cy) swap(cx, cy);
    for (int r = rx + 1; r < ry; ++r)
    for (int c = cx + 1; c < cy; ++c)
        if (!use[rc2x(r, c)]) return false;
    return true;
}

void next(int pos = 0) {
    if (pos >= L) ++cnt;
    if (pos == M) return ;
    for (int i = 0; i < M; ++i)
    {
        if (use[i]) continue;
        if (pos && !check(a[pos-1], i)) continue;
        use[i] = 1;
        a[pos] = i;
        next(pos + 1);
        use[i] = 0;
    }
}

int main() {
    next();
    printf("%lld\n", cnt);
    return 0;
}