python破解手机锁屏密码_手机屏幕解锁模式

36

可以通过DFS的方式先计算出刚好按下n个键时有多少种组合，然后求出S[n]至S[M]的和。

DFS的主要难度在于，下一步可以与当前的位置不直接相连。这时分两种情况：

1. 普通的八个方向 (上下左右以及其45度夹角方向)：

若这八个方向都已经越界或走过了，则这时无路可走。若是普通的DFS则返回，但是九宫格解锁可以跳过相邻的一格。注意只能在这八个方向跳多一步，相当于踩着已经被按下的位置再沿着相同方向走一步。

2.其余的八个方向

其余的八个方向虽然不直接与当前位置直接相连，但是它与当前位置的连线不会触碰到其他位置，因此也可以直接到达。

以下为DFS代码

int dir[16][2] = {//16个方向

{ -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 },

{ 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 },

{-2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 },

{ 2, -1 }, { 1, -2 }, { -1, -2 }, { -2, -1 }

};

int isVisit[5][5];//是否已按下

bool canVisit(int i, int j){//判断能否按下

if (i 3 || j 3 || isVisit[i][j]) return false;

return true;

}

int times[10];

//d:已经被选中的键的个数(深度)

void DFS(int i, int j, int d){

if (d == 9){