以下是该程序的题目要求，如下：编程题：Android手机9宫格有多少种可能的手势？如果是16宫格呢？ 规则：4个点或以上的手势才算；一个手势中，每个点最多只能被算作经过一次；只有已经经过的点才能直接越过，也就是说，如果你想连接的两个点中间还有其他点，那这些点必须是已经被之前经过的。
解题思路：1、本题从数学角度也可以解出来，但是比较复杂。若程序实现，可以从遍历树结构或者动态规划的角度实现，但是在保存现场中可以用到栈或者队列。2、本人从三个模块入手，第一个模块是初始化模块，用于初始化初始的连接矩阵，构造一个可连接矩阵，1表示可连接，0表示不可连接。第二个模块用于计算新的连接矩阵，根据之前遍历过得节点修改连接矩阵。第三个模块用于递归遍历树。
程序代码如下：
代码块
include “stdio.h”
define FALSE 0
define TRUE 1
//commonset
int mode;//0 equal to 9GongGe,1 equal to 16Gongge
int level = 0;
int layer = 4;
long int count=0;
int stat[9]={FALSE};
int C_List[9]={0};
int StarterDirection[9][9]=
{
//1,2,3,4,5,6,7,8,9 node
{0,1,0,1,1,1,0,1,0},
{1,0,1,1,1,1,1,0,1},
{0,1,0,1,1,1,0,1,0},
{1,1,1,0,1,0,1,1,1},
{1,1,1,1,0,1,1,1,1},
{1,1,1,0,1,0,1,1,1},
{0,1,0,1,1,1,0,1,0},
{1,0,1,1,1,1,1,0,1},
{0,1,0,1,1,1,0,1,0},
};
int direction[9][9]=
{
//1,2,3,4,5,6,7,8,9 node
{0,1,0,1,1,1,0,1,0},
{1,0,1,1,1,1,1,0,1},
{0,1,0,1,1,1,0,1,0},
{1,1,1,0,1,0,1,1,1},
{1,1,1,1,0,1,1,1,1},
{1,1,1,0,1,0,1,1,1},
{0,1,0,1,1,1,0,1,0},
{1,0,1,1,1,1,1,0,1},
{0,1,0,1,1,1,0,1,0},
};
//
int CaculateRouter(int stat[9])
{
//caculate the node direction
int i,j;
for(i=0;i<9;i++)
{
for(j=0;j<9&&direction[i][j]==0;j++)
{
if((i+j)/2.0-int((i+j)/2.0) == 0.0 && stat[(i+j)/2]==TRUE&&i!=j)//
direction[i][j]=1;
}
}
for(i=0;i<9;i++)
{
if(stat[i]==TRUE)//fix the matrix of CanGet,cut the havelinked node
for(j=0;j<9;j++)
direction[j][i]=0;
}
return 1;
}
int Build(int node,int level)//level start from 0
{
if(level== layer-1)
{
count++;
//printf("Find One!----%ld\n",count);
return 1;
}
for(int k=0;k<9;k++)
{
if(direction[node][k]==1)
{
int i,j;
//临时存储现场
int temp1[9][9];
int stat1[9];
for(i=0;i<9;i++)
stat1[i]=stat[i];
for(i=0;i<9;i++)
for(j=0;j<9;j++)
temp1[i][j]=direction[i][j];
stat[node]=TRUE;
level ++;
//以上为保存现场
CaculateRouter(stat);
Build(k,level);
//恢复现场
stat[node]=FALSE;
level--;
node++;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
direction[i][j]=temp1[i][j];
for(i=0;i<9;i++)
stat[i]=stat1[i];
}
}
}
/*
if (level == layer)
{
count++;
level--;
printf("\n Find One!!!\n");
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
directionPoint[i][j]=direction[i][j];
return 1;
}
while(node<9)
{
if(stat[node]==TRUE)
return 0;
int j=0;
stat[node]=TRUE;
printf("%d-->",node);
while(j<9 )
{
if(directionPoint[node][j] == 1)
{
CaculateRouter(stat,directionPoint);
level++;
DFS9GongGe(stat,j,level,directionPoint);
}
j++;
}
stat[node]=FALSE;
node++;
return 1;
}
return 1;
*/
int main()
{
int Pointdirection[9][9]=
{
//1,2,3,4,5,6,7,8,9 node
{0,1,0,1,1,1,0,1,0},
{1,0,1,1,1,1,1,0,1},
{0,1,0,1,1,1,0,1,0},
{1,1,1,0,1,0,1,1,1},
{1,1,1,1,0,1,1,1,1},
{1,1,1,0,1,0,1,1,1},
{0,1,0,1,1,1,0,1,0},
{1,0,1,1,1,1,1,0,1},
{0,1,0,1,1,1,0,1,0},
};
int num=4;
while(num<=9)
{
layer =num;
num++;
Build(0,0);
}
printf("Total = %ld",count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
脚注
对代码几点解释：
1、代码有部分冗余，但是完全可以运行
2、矩阵为连接矩阵，每次递归需要修改
3、通过全局变量实现对程序的控制。
4、程序结果可以妙出，但是对于16个点的四乘四矩阵运算时间较长，下次发文会对4X4矩阵的算法。
5、通过该程序对递归程序的有了一定了解，在编译器阶段，将程序不是debug版本，直接出exe可执行文件。利用IDA反编译程序，发现程序在编译阶段进行了一定的优化。下一步准备改造程序，利用栈和队列构造生成树，不采用递归算法。
程序生成结果
---------------------
作者：二进制程序猿
原文：/syh_486_007/article/details/50837768
版权声明：本文为博主原创文章，转载请附上博文链接！
![九宫格C语言递归程序 [置顶] C语言递归实现N宫格（九宫格）源码](https://2000zi.500zi.com/uploadfile/img/14/831/2b55f97682c8db01c098c37ae3b6e439.jpg)
