number of patterns of android unlock screen

android-unlock.c

#include <stdio.h>

int visited[9] = {0};
int nsteps = 0;

/* alternate can_connect */
int max(int x, int y)
{
    return x >= y? x: y;
}

int min(int x, int y)
{
    return x <= y? x: y;
}

int can_connect1(int i, int j)
{
    int x1 = i / 3, y1= i % 3;
    int x2 = j / 3, y2= j % 3;
    int dx = max(x1, x2) - min(x1, x2);
    int dy = max(y1, y2) - min(y1, y2);
    int mx = (x1+x2) / 2;
    int my = (y1+y2) / 2;
    int m = (i + j) / 2;
    if (((dx * dy == 0 && dx + dy == 2) ||
         (dx == 2 && dy == 2)) &&
        !visited[m])
        return 0;
    return 1;
}
/* */

int can_connect(int i, int j)
{
    int x1 = i / 3, y1= i % 3;
    int x2 = j / 3, y2= j % 3;
    int mx = (x1+x2) / 2;
    int my = (y1+y2) / 2;
    int m = (i + j) / 2;
    if (x1+x2 == mx * 2 && y1+y2 == my * 2 && !visited[m])
        return 0;
    return 1;
}

int track(int p)
{
    int npath = 0;
    int i;
    visited[p] = 1;
    nsteps++;
    if (nsteps >= 4)
        npath++;
    for (i = 0; i < 9; i++) {
        if (visited[i] || !can_connect(p, i))
            continue;
        npath += track(i);
    }
    visited[p] = 0;
    nsteps--;
    return npath;
}

int solve()
{
    int ret = 0;

    ret += 4 * track(0);
    ret += 4 * track(1);
    ret += track(4);
    return ret;
}

int main()
{
    printf("%d\n", solve());
    return 0;
}