[转]Android的绘图密码有多少种可能性

转自 http://blog.sina.com.cn/s/blog_7d34486c0100zqkv.html，有看懂的高人给分析一下

用过Android的人应该知道，Android有一种绘图密码。3×3一共9个点，手指连续划过这些点，每一种绘图方式就是一种密码。那么这种绘图密码一共多少种可能性呢？

先提供4个假设：

1.假设绘图中覆盖的点的有效个数可以从1到9

2.每个点都可以是起始点

3.每个点被覆盖过后，就不能再连接第二次了，但是可以被再次路过。

4.每个点都可以直接连接到任何一个点，除了一种情况，就是这两个点之间还有另一个点没被覆盖过。

关于3，4的解释：

ABC

DEF

GHI

假设9个点分别是A到I，显然A可以直接连接BDEFH（假设这几个点没被覆盖过)，但是A能否直接连接CGI这取决于BDE是否被覆盖了，如果B被覆盖了，那么A可以直接连接到C，这时我们称A路过B连接到C。否则A需要先连接到B，然后才能连接到C。其他的类似。

那么怎么求有多少种不同方案呢，动态规划是比较容易想到的一个方法。

用一个bits mask存储这9个点的状态，这个bits mask有9位，每一位是0表示这个点没有被覆盖，反之被覆盖。

用一个三维数组count[9][9][2^9]来存储状态，

第一维表示覆盖的点的个数，0代表只覆盖1个点，1代表覆盖两个点,以此类推

第二维表示路径的始发点，0代表第一个点，8代表最后一个点

第三维表示目前9个点的状态。

显然我们要求的答案是 Sum{count[i][j][0]}, i,j=0,...,8

写个程序算一下。一共389497种。看起来Android密码还是比较安全的。

刚才在网上找了一个文章，证明我程序的正确性。http://bbs.ptbus.com/thread-246829-1-1.html

原来Android手机绘图密码最短长度为4，我没用过Android手机，只是玩了下别人的绘图密码界面呵呵。

那么最后Sum{count[i][j][0]}, i=3,...8; j=0,...,8就是答案。这样答案就是389112和上面文章中的结论一致。

#include

using namespace std;

int main()

{

int count[9][9][1<<9];

memset(count, 0, sizeof(count));

for(int i = 0; i < 9; i++)

for(int j = 0; j < 9; j++)

for(int m = 0; m < (1<<9); m++)

{

// point j is already covered

if (((1 << j) & m) != 0)

{

continue;

}

// only need cover 1 point

if (i == 0)

{

count[i][j][m] = 1;

}

else

{

// generate new mask

int newMask = (m | (1<

// pick up next point

for(int next = 0; next < 9; next++)

{

// point next is already covered

if (((1 << next) & newMask) != 0)

{

continue;

}

int x, y, nx, ny;

x = j/3;

y = j%3;

nx = next/3;

ny = next%3;

// there is a inter point between point j and point next

if ((x+nx)%2 == 0 && (y+ny)%2 == 0)

{

int midx = (x+nx)/2;

int midy = (y+ny)/2;

int inter = midx*3 + midy;

// inter point is not covered now

// so we can't choose point next

if (((1 << inter) & newMask) == 0)

{

continue;

}

// choose point next

count[i][j][m] += count[i-1][next][newMask];

}

int ans = 0;

for(int i = 0; i < 9; i++)

for(int j = 0; j < 9; j++)

{

ans += count[i][j][0];

}

cout << ans << endl;

}

更多相关文章

随机推荐