首页 > 代码库 > 马踏棋盘的c语言实现（一.遍历法）
马踏棋盘的c语言实现（一.遍历法）
题目很简单呀！！！
在国际象棋的棋盘上，将马随意放置，之后走日字，走完即可。
要求：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: 574932286@qq.com 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 else102 {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 else115 {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 else128 {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 else200 {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 }
马踏棋盘的c语言实现（一.遍历法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。