Skip to content

Instantly share code, notes, and snippets.

@zhangsen
Created May 13, 2012 11:01
Show Gist options
  • Save zhangsen/2687787 to your computer and use it in GitHub Desktop.
Save zhangsen/2687787 to your computer and use it in GitHub Desktop.
number of patterns of android unlock screen
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment