图的遍历-马踏棋盘算法/骑士周游

奥普瓯江

原理：




备注：占时想不出更好的方法改编这个算法，先理解



代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAX 6
   
5. 
   
6. int chess[MAX][MAX];
   
7. 
   
8. 
   
9. int get_chess(int x, int y, int tag);
   
10. int judge_chess(int *x, int *y, int count);
    
11. void pri_chess();
    
12. 
    
13. void pri_chess()                        //打印棋盘，因为是全局变量所以直接打印即可
    
14. {
    
15.     for(int i = 0; i < MAX; i++)
    
16.     {
    
17.         for(int j = 0; j < MAX; j++)
    
18.         {
    
19.             printf("%4d", chess[i][j]);
    
20.         }
    
21.         putchar('\n');
    
22.     }
    
23. }
    
24. int judge_chess(int *x, int *y, int count)          //对八个方向进行判断，如判断成立赋予指针x或y新值
    
25. {
    
26.     switch(count)
    
27.     {
    
28.         case 0:{
    
29.             if(*x - 2 >= 0 && *y - 1 >= 0 && chess[*x - 2][*y - 1] == 0)        //左上
    
30.             {
    
31.                 *x = *x - 2;                        //上面的if判断赋予指针新值
    
32.                 *y = *y - 1;
    
33.                 return 1;
    
34.             }
    
35.             break;
    
36.         }
    
37.         case 1:{
    
38.             if(*x - 2 >= 0 && *y + 1 < MAX && chess[*x - 2][*y + 1] == 0)        //左下
    
39.             {
    
40.                 *x = *x - 2;
    
41.                 *y = *y + 1;
    
42.                 return 1;
    
43.             }
    
44.             break;
    
45.         }
    
46.         case 2:{
    
47.             if(*x - 1 >= 0 && *y + 2 < MAX && chess[*x - 1][*y + 2] == 0)        //下左
    
48.             {
    
49.                 *x = *x - 1;
    
50.                 *y = *y + 2;
    
51.                 return 1;
    
52.             }
    
53.             break;
    
54.         }
    
55.         case 3:{
    
56.             if(*x + 1 < MAX && *y + 2 < MAX && chess[*x + 1][*y + 2] == 0)        //下右
    
57.             {
    
58.                 *x = *x + 1;
    
59.                 *y = *y + 2;
    
60.                 return 1;
    
61.             }
    
62.             break;
    
63.         }
    
64.         case 4:{
    
65.             if(*x + 2 < MAX && *y + 1 < MAX && chess[*x + 2][*y + 1] == 0)        //右下
    
66.             {
    
67.                 *x = *x + 2;
    
68.                 *y = *y + 1;
    
69.                 return 1;
    
70.             }
    
71.             break;
    
72.         }
    
73.         case 5:{
    
74.             if(*x + 2 < MAX && *y - 1 >= 0 && chess[*x + 2][*y - 1] == 0)        //右上
    
75.             {
    
76.                 *x = *x + 2;
    
77.                 *y = *y - 1;
    
78.                 return 1;
    
79.             }
    
80.             break;
    
81.         }
    
82.         case 6:{
    
83.             if(*x + 1 < MAX && *y - 2 >= 0 && chess[*x + 1][*y - 2] == 0)        //上右
    
84.             {
    
85.                 *x = *x + 1;
    
86.                 *y = *y - 2;
    
87.                 return 1;
    
88.             }
    
89.             break;
    
90.         }
    
91.         case 7:{
    
92.             if(*x - 1 >= 0 && *y - 2 >= 0 && chess[*x - 1][*y - 2] == 0)        //上左
    
93.             {
    
94.                 *x = *x - 1;
    
95.                 *y = *y - 2;
    
96.                 return 1;
    
97.             }
    
98.             break;
    
99.         }
    
100.         default:
     
101.             break;
     
102.        /*case 0:
     
103.                         if( *x+2 < MAX && *y-1>=0 && chess[*x+2][*y-1]==0 )        // 右上               //验证
     
104.                         {
     
105.                                 *x = *x + 2;
     
106.                                 *y = *y - 1;
     
107.                                 return 1;
     
108.                         }
     
109.                         break;
     
110. 
     
111.                 case 1:
     
112.                         if( *x+2 < MAX && *y+1 < MAX && chess[*x+2][*y+1]==0 )        //右下
     
113.                         {
     
114.                                 *x = *x + 2;
     
115.                                 *y = *y + 1;
     
116.                                 return 1;
     
117.                         }
     
118.                         break;
     
119. 
     
120.                 case 2:
     
121.                         if( *x+1 < MAX && *y-2 >= 0 && chess[*x+1][*y-2]==0 )                 //上右
     
122.                         {
     
123.                                 *x = *x + 1;
     
124.                                 *y = *y - 2;
     
125.                                 return 1;
     
126.                         }
     
127.                         break;
     
128. 
     
129.                 case 3:
     
130.                         if( *x+1 < MAX && *y+2 < MAX && chess[*x+1][*y+2]==0 )        //下右
     
131.                         {
     
132.                                 *x = *x + 1;
     
133.                                 *y = *y + 2;
     
134.                                 return 1;
     
135.                         }
     
136.                         break;
     
137. 
     
138.                 case 4:
     
139.                         if( *x-2 >= 0 && *y-1 >= 0 && chess[*x-2][*y-1]==0 )                //左上
     
140.                         {
     
141.                                 *x = *x - 2;
     
142.                                 *y = *y - 1;
     
143.                                 return 1;
     
144.                         }
     
145.                         break;
     
146. 
     
147.                 case 5:
     
148.                         if( *x-2 >= 0 && *y+1 < MAX && chess[*x-2][*y+1]==0 )                //左下
     
149.                         {
     
150.                                 *x = *x - 2;
     
151.                                 *y = *y + 1;
     
152.                                 return 1;
     
153.                         }
     
154.                         break;
     
155. 
     
156.                 case 6:
     
157.                         if( *x-1 >= 0 && *y-2 >= 0 && chess[*x-1][*y-2]==0 )                //上左
     
158.                         {
     
159.                                 *x = *x - 1;
     
160.                                 *y = *y - 2;
     
161.                                 return 1;
     
162.                         }
     
163.                         break;
     
164. 
     
165.                 case 7:
     
166.                         if( *x-1 >= 0 && *y+2 < MAX && chess[*x-1][*y+2]==0 )                //下左
     
167.                         {
     
168.                                 *x = *x - 1;
     
169.                                 *y = *y + 2;
     
170.                                 return 1;
     
171.                         }
     
172.                         break;
     
173. 
     
174.                 default:
     
175.                         break;*/
     
176. 
     
177.     }
     
178.     return 0;
     
179. }
     
180. 
     
181. int get_chess(int x, int y, int tag)
     
182. {
     
183.     int lx = x, ly = y, flag = 0, count = 0;
     
184. 
     
185.     chess[x][y] = tag;                               //初始传入函数中的1这个值先传如棋盘，这个永远不会变
     
186. 
     
187.     if(tag == MAX * MAX)
     
188.     {
     
189.         pri_chess();
     
190.         return 1;
     
191.     }
     
192.     flag = judge_chess(&lx, &ly, count);              //第一个judge_chess判断，开始传入的肯定是0因为count开始被赋予0这个值
     
193. 
     
194.     while(flag == 0 && count < MAX)                 //如果第一个judge_chess返回来的是0这个值那么及执行这个循环，这里有一个count++意思是在第一个judge_chess返回值同等的位置进行剩余方位的筛选
     
195.     {
     
196.         count++;                                    //剩余方位进行定位
     
197.         flag = judge_chess(&lx, &ly, count);        //筛选
     
198.     }
     
199. 
     
200.     while(flag)                                    //如果在第一个judge_chess判断返回的是1这个值及执行这个循环
     
201.     {
     
202.         if(get_chess(lx, ly, tag + 1))              //如果执行了while这个循环及这个if判断执行递归循环把tag+1这个值传入开始的chess棋盘中，如果get_chess递归逆释放中返回的是0
     
203.         {
     
204.             return 1;
     
205.         }
     
206. 
     
207.         lx = x;                                     //x、y值在逆释放的时候变化了，但是lx、ly未被从新赋值，所以这里需要x、y向其从新赋值
     
208.         ly = y;
     
209. 
     
210.         count++;                                    //count逆释放时被返回两个数，如循环失败再次对方向进行从新判断在这个时候count不归零而是用递归释放的数据
     
211.         flag = judge_chess(&lx, &ly, count);
     
212. 
     
213.         while(flag == 0 && count < MAX)
     
214.         {
     
215.             count++;
     
216.             flag = judge_chess(&lx, &ly, count);
     
217.         }
     
218.     }
     
219.     if(flag == 0)                                   //当递归执行逆释放之前会先执行该判断，因为棋盘走不下去了所以返回前先对该位置回复未输入数据的状态也就是从新赋值为0
     
220.     {
     
221.         chess[x][y] = 0;
     
222.     }
     
223. 
     
224.     return 0;
     
225. 
     
226. }
     
227. 
     
228. int main()
     
229. {
     
230.     for(int i = 0 ; i < MAX; i++)           //初始化棋盘
     
231.     {
     
232.         for(int j = 0; j < MAX; j++)
     
233.         {
     
234.             chess[i][j] = 0;
     
235.         }
     
236.     }
     
237. 
     
238.     if(!get_chess(2, 0, 1))                 //函数调用并赋予初始棋子坐标及值
     
239.     {
     
240.         printf("马踏棋盘失败了！");
     
241.     }
     
242. 
     
243.     return 0;
     
244. }
     

复制代码

输出：