手机的九宫格图案解锁总共能绘出多少种图案？（hiho模拟面试题2 - google在线技术笔试模拟）

手机的九宫格图案解锁总共能绘出多少种图案？（hiho模拟面试题2 - google在线技术笔试模拟）

尚未经过的点。此外，这条折线还需要至少经过4个点。

尚未经过的点2。2->4->1->3->6是合法的，因为1->3时点2已经被划过了。

无意中看到了这道题 而且在知乎回答中 各种语言啊  于是我今天上午无聊时也想做做了  哈哈

我可是没看别人的代码  看了正确结果~  因为感觉搜索搜来搜去 好爽啊  就按照自己想的写了

​

使用DFS（深搜即可）  遍历所有可能的情况  然后筛选不可能的情况

首先使用一个数组 把不可能出现的情况列出

filter[1][3]=filter[3][1]=2; filter[4][6]=filter[6][4]=5; filter[7][9]=filter[9][7]=8; filter[1][7]=filter[7][1]=4; filter[2][8]=filter[8][2]=5; filter[3][9]=filter[9][3]=6; filter[1][9]=filter[9][1]=5; filter[3][7]=filter[7][3]=5;

然后深搜的同时也进行筛选

void dfs(int count){ if(count>=4) { result++; } for(int i=1;i<=9;i++) { if(count>0&&!vis[filter[stamp[count-1]][i]]) continue; if(!vis[i]) { vis[i]=1; stamp[count]=i; dfs(count+1); vis[i]=0; } } return ;}

全部代码：

#include #include int filter[10][10];int stamp[9];bool vis[10];int result;void dfs(int count){ if(count>=4) { result++; } for(int i=1;i<=9;i++) { if(count>0&&!vis[filter[stamp[count-1]][i]]) continue; if(!vis[i]) { vis[i]=1; stamp[count]=i; dfs(count+1); vis[i]=0; } } return ;}int main(){ memset(filter,0,sizeof(filter)); filter[1][3]=filter[3][1]=2; filter[4][6]=filter[6][4]=5; filter[7][9]=filter[9][7]=8; filter[1][7]=filter[7][1]=4; filter[2][8]=filter[8][2]=5; filter[3][9]=filter[9][3]=6; filter[1][9]=filter[9][1]=5; filter[3][7]=filter[7][3]=5; result=0; vis[0]=true; dfs(0); printf("%d\n",result);}

结果：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。