-
-
[原创][公布答案]发个小程序给逆向新手们玩
-
发表于: 2014-11-17 20:38
-
说明：这是上午在写一个算法题的时候碰到的，真心不难，只为活跃逆向版块
要求：分析其算法，最好能解析其功能
ps:如果有同学玩的话，后面会放出源码
问题背景：
手机的九宫格图案解锁总共能绘出多少种图案？
需要满足的要求有：
至少经过四个点；
不能重复经过同一个点；
路径上的中间点不能跳过（如从1到3一定会经过2）；
如果中间的点是之前已经用过的，那么这个点就可以被跳过（如213，因为2已经被用过，1就可以越过2与3连接，132是不允许的）。
没啥东西，其实说白了，就是一个深度优先搜索
要求：分析其算法，最好能解析其功能
ps:如果有同学玩的话，后面会放出源码
问题背景：
手机的九宫格图案解锁总共能绘出多少种图案？
需要满足的要求有：
至少经过四个点；
不能重复经过同一个点；
路径上的中间点不能跳过（如从1到3一定会经过2）；
如果中间的点是之前已经用过的，那么这个点就可以被跳过（如213，因为2已经被用过，1就可以越过2与3连接，132是不允许的）。
没啥东西，其实说白了，就是一个深度优先搜索
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int flag[10]; //标识该点是否被访问过
int exist[10][10]; //标识两点之间是否存在其它的点
int count; //标识可行的方案数
void init()
{
memset(flag,0,sizeof(flag));
exist[1][3] = 1;
exist[1][7] = 1;
exist[1][9] = 1;
exist[2][8] = 1;
exist[3][1] = 1;
exist[3][7] = 1;
exist[3][9] = 1;
exist[4][6] = 1;
exist[6][4] = 1;
exist[7][1] = 1;
exist[7][3] = 1;
exist[7][9] = 1;
exist[8][2] = 1;
exist[9][1] = 1;
exist[9][3] = 1;
exist[9][7] = 1;
}
void DFS(int *fg, int exist[10][10], int n, int cur_point, int total_point_count)
{
int i;
if (total_point_count == n) {
count++;
}
else {
for (i = 1; i <= 9; i++) {
if (!fg[i] && (!exist[cur_point][i] || (exist[cur_point][i] && fg[(cur_point + i) / 2]))) {
fg[i] = 1;
DFS(fg, exist, n , i, total_point_count + 1);
fg[i] = 0;
}
}
}
}
int main()
{
int start,point_count;
for (point_count = 4; point_count <= 9; point_count++) {
for (start = 1; start <= 9; start++) {
init();
flag[start] = 1;
DFS(flag, exist, point_count, start, 1);
}
}
printf("%d\n",count);
system("pause");
return 0;
}
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
  一点都不开心为此刚学了if语言的判断，发现一直在压栈，跟到心憔悴 。明天继续跟
|
|
|
|
|
|
|
