马踏棋盘的c语言实现（一.遍历法）

浏览数：73 / 时间：2015年06月08日

题目很简单呀！！！

在国际象棋的棋盘上，将马随意放置，之后走日字，走完即可。

要求：8×8的棋盘

遍历算法：

可以说是碰运气，当你确定在某一位置时，根据规则你自然有了八种选择，


	2		3
1				4
		H
8				6
	7		5

分别是

X= {i-2, i-1, i+1, i+2, i+2, i+1, i-1, i-2};

Y= {i-1, i-2, i-2, i-1, i+1, i+2, i+2, i+1};

往简单了想，当其越界或是已被占有，下一个位置的可能去向就会减少，你要做的就是检验当前步的下一步的情况中有那个是可以走，那个不可以，可以了就直接往下走，不行就跳到下一步。但注意当八种情况都不行时就必须可以回溯到上一步的位置

（重点在于获得上一步往下一步走选路情况，以便你不会再走同样的路）。幸运的话，也许能出来，不幸的话，就和我的同学一样，跑了三个小时还是没出结果。

使用的数据结构是三个整型栈，分别存放x，y，t（当前步如何走向下一步）

注意以下代码只能跑出（2,3）的位置，其他位置不是待检验，就是跑时间太长

人如果你想检验正确与否，就将代码中宏定义的64,8改为36,6(其他也可以吧)，检验之后是能跑的

  1 /*************************************************************************
  2     > File Name: mataqipan.c
  3     > Author: zh
  4     > Mail: [email protected] 
  5     > Created Time: 2014年09月28日 星期日 16时21分10秒
  6     > 实现马踏棋盘
  7   8  ************************************************************************/
  9 #include<stdio.h>
 10 #include<stdlib.h>
 11 #define STACKSIZE 64 
 12 #define MAPSIZE 8 //
 13 #define FALSE 0
 14 #define TURE 1
 15 
 16 typedef struct stack * Stack;
 17 typedef int ElementType;
 18 
 19 int IsEmpty( Stack S );
 20 int IsFull( Stack S );
 21 Stack CreateStack( void  );
 22 int Push( Stack S, ElementType X );
 23 ElementType Pop( Stack S );
 24 ElementType Top( Stack S );
 25 int IntTest( int i, int j );
 26 int Test( int i, int j, int  Map[][MAPSIZE] );
 27 void Hua( int i, int j, int Map[][MAPSIZE] );
 28 void ReHua( int i, int j, int Map[][MAPSIZE] );
 29 
 30 
 31 struct stack{
 32     int top;
 33     ElementType Array[STACKSIZE];
 34 };
 35 
 36 int IsEmpty( Stack Q )
 37 {
 38     return Q->top == -1;
 39 }/*IsEmpty*/
 40 
 41 int IsFull( Stack Q )
 42 {
 43     return Q->top == STACKSIZE-1;
 44 }/*IsFull*/
 45 
 46 /*创建一个存放64个整型数的栈*/
 47 Stack CreateStack( void )
 48 {
 49     Stack S;
 50     S = (Stack)malloc(sizeof(struct stack));
 51 
 52     if( S == NULL )
 53     {
 54        exit(1);
 55     }
 56     S->top = -1;
 57     return S;
 58 }/*CreateStack*/
 59 
 60 int Push( Stack S, ElementType X )
 61 {
 62     if( IsFull(S) )
 63     {
 64         return FALSE;
 65     }
 66     else
 67     {
 68          S->top++;
 69         S->Array[S->top] = X;
 70         return TURE;
 71     }
 72 }/* Push */
 73 
 74 /* 出栈并且返回出栈的值 */
 75 ElementType Pop( Stack S )
 76 {
 77     int temp;
 78     if( IsEmpty(S) )
 79     {
 80         printf("栈空\n");
 81         getchar();
 82         exit(0);
 83     }
 84     else
 85     {
 86         temp=S->top;
 87         S->top--;
 88         return S->Array[temp];
 89     }
 90 }/* Pop */
 91 
 92 /* 输出栈顶元素 */
 93 ElementType Top( Stack S )
 94 { 
 95     if( IsEmpty(S) )
 96     {
 97         printf("栈空\n");
 98         system("PAUSE");
 99         exit(0);
100     }
101     else
102     {
103         return S->Array[S->top];
104     }
105 }/* Top */
106 
107 /* 检验被初始化的i,j 是否越位,没有越位返回TURE，否则返回FLASE */
108 int  IntTest( int i, int j )
109 {
110     if( i>=0 && i<MAPSIZE && j>=0 && j<MAPSIZE )
111     {
112         return TURE;
113     }
114     else
115     {
116         return FALSE;
117     }
118 }/* IntTest */
119 
120 /* 判断该位置是否已经被占和该位置是否越位，符合条件返回TURE ，否则返回FLASE*/
121 int Test( int i, int j, int Map[][MAPSIZE] )
122 {
123     if( Map[i][j]==1 || !IntTest(i,j) )//判断该位置是否已经被占和该位置是否越位
124     {
125         return FALSE;
126     }
127     else
128     {
129         return TURE;
130     }
131 }/* Test */
132 
133 /* 为MAP做标记 */
134 void Hua( int i, int j, int Map[][MAPSIZE] )
135 {
136     Map[i][j] = TURE;
137 }/* Hua */
138 
139 /* 消除Map上的标记 */
140 void ReHua( int i, int j, int Map[][MAPSIZE] )
141 {
142     Map[i][j] = FALSE;
143 }/* ReHUa */
144 
145 int main( void )
146 {
147     Stack A, B, C ;/*3个栈分别用来存储 i,j.t[下一步棋在当前步棋八个位置中的那一个]*/
148     int Map[MAPSIZE][MAPSIZE]={0};
149     int a[8]={-2,-1, 1, 2,2,1,-1,-2};
150     int b[8]={-1,-2,-2,-1,1,2, 2, 1};
151     int i,j,t;
152     int temp;
153 
154     A = CreateStack();
155     B = CreateStack();
156     C = CreateStack();//栈的初始化
157     do{
158     printf("输入x ：");
159     scanf("%d",&i);
160     printf("输入y ：");
161     scanf("%d",&j);
162     temp=IntTest( i, j );//测试输入
163     }while(!temp );
164 
165     Hua( i, j, Map);
166     Push( A, i );
167     Push( B, j );
168     Push( C, -1 );
169     
170     while( !IsFull(A) )
171     {
172         
173             if( IsEmpty( A ) )
174             { printf("Oh No, why ,shit ,fuck,come up \n");
175               printf(" 不可能有这种走法\n");
176             getchar();  
177               exit(0);
178             }
179         //栈空的可能性
180 
181         i = Top( A );
182         j = Top( B );
183         t = Top( C )+1;
184         
185         while( t<=8-1  && !Test( a[t]+i, b[t]+j , Map ) )   //    
186         {
187             t++;
188             if( t == 8 )
189                 break;
190         }//while,用以判断8种可能那种不合适
191     
192         if( t == 8 )
193         {
194             i = Pop( A );
195             j = Pop( B );
196             Pop( C );
197             ReHua( i, j, Map );
198         }//回溯到上一步
199         else
200         {
201             Push( A, a[t]+i );
202             Push( B, b[t]+j );
203             Pop( C );
204             Push( C, t );
205             Push( C, -1 );
206             Hua( a[t]+i, b[t]+j, Map );
207         }// 下一步被确认，将i，j，t 放入栈中，并将-1放入栈,在map上标记该步
208 
209     }
210     printf("OK\n");
211     getchar();
212     for( i=0; i<MAPSIZE; i++ )
213         for( j=0; j<MAPSIZE; j++ )
214         {
215            Map[A->Array[i*MAPSIZE+j]][B->Array[i*MAPSIZE+j]]=i*MAPSIZE+j;
216         }
217     for( i=0; i<MAPSIZE; i++ )
218         for( j=0; j<MAPSIZE; j++ )
219         {
220             printf("%5d",Map[i][j]);
221             if( j == MAPSIZE-1 )
222                 printf("\n");
223         }
224      getchar();
225      return 0;
226 }