一道有意思的手机九宫格手势密码的算法题，大家看看有好的思路吗

[yasonyyx]

今天看到一道九宫格，就是手机手势密码的题，题目大概是这样的：
1、如果只设置2位密码，有多少种满足的密码，密码不能穿越，比如1 3之间穿过2，这是不允许的；2、如果变成N*M格，判断一个2位密码是否是满足要求的密码（要求同1），
3、如果设置密码位数为9位，有多少种合适的密码，给出算法思路，并给出伪代码。

我的想法是这样的：
先检测当前位置在哪，再穷举所有移动记录次数。
1、3*4+5*4+1*8=40.
2、可以用一个N*M的数组保存1~N*M的值，然后看两位密码是否接触...
3、实在没想到什么让自己觉得很好的思路...

各位大神看看除了我这个思路外还有什么更高效的方法吗？

[sam12321]

已经按过的点貌似不能再按了

[gooffer]

穷举吧，这个没方法的吧？

[deljuven]

类似n皇后问题，回溯吧。。。还没有想到更好的思路。。。

[xylophone21]

歪个楼吧,为什么要计算密码是否满足要求?为什么要计算有多少种情况?

密码保存模块校验? 这不是把密码保存和输入耦合吗?
密码输入模块校验?人都能输进去了你担心这个干啥?怕UI bug?万一UI Bug了用更高级的密码重置一下不就OK了?不会没有吧?
计算密码的安全性? 那就不需要在板子上计算了,找台服务器慢慢算就是,一次性的工作,为什么要高效?

[pheyer]

第1题，九宫格从左上角顶点开始，从左到右从上到下分别命令为A, B, ..., I, J。统计规则：每个点只统计右方，右下方，下方，左下方的连接点。则A点的连接点个数为3个，B点的连接点为4个，C点的连接点为2个，D、E、F与A、B、C一致，H和I分别为一个。
这样就能找到规律了吧：(n-1)*(3+(m-2)*4+2) + m-1

第2题，如果是4宫格，合适的密码为3^9吗？感觉有点难度

[pheyer]

点过的好像不能再点吧，那就不是3^9了。