|
10鱼币
本帖最后由 gascd 于 2017-1-26 12:26 编辑
代码和小甲鱼的对照了,除了nextxy()函数以外,其他的函数都差不多。然而我的nextxy()函数就算不出解来,而小甲鱼的nextxy()函数就能够算出来。
如下为代码:
- #include <stdio.h>
- #include <time.h>
- #include <stdlib.h>
- #define X 8
- #define Y 8
- int chess[X][Y];
- #if 0
- //小甲鱼的正确的代码
- int nextxy(int *x, int *y, int count)
- {
- switch(count)
- {
- case 0:
- if( *x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0 )
- {
- *x = *x + 2;
- *y = *y - 1;
- return 1;
- }
- break;
- case 1:
- if( *x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0 )
- {
- *x = *x + 2;
- *y = *y + 1;
- return 1;
- }
- break;
- case 2:
- if( *x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0 )
- {
- *x = *x + 1;
- *y = *y - 2;
- return 1;
- }
- break;
- case 3:
- if( *x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0 )
- {
- *x = *x + 1;
- *y = *y + 2;
- return 1;
- }
- break;
- case 4:
- if( *x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0 )
- {
- *x = *x - 2;
- *y = *y - 1;
- return 1;
- }
- break;
- case 5:
- if( *x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0 )
- {
- *x = *x - 2;
- *y = *y + 1;
- return 1;
- }
- break;
- case 6:
- if( *x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0 )
- {
- *x = *x - 1;
- *y = *y - 2;
- return 1;
- }
- break;
- case 7:
- if( *x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0 )
- {
- *x = *x - 1;
- *y = *y + 2;
- return 1;
- }
- break;
- default:
- break;
- }
- return 0;
- }
- #endif
- #if 1
- //我的错误代码
- // 判断下一步能不能走
- int nextxy(int *x, int *y, int count)
- {
- switch(count)
- {
- case 0:if((*x)-1>=0 && (*y)+2<=Y-1 && chess[*x-1][*y+2]==0)
- {
- *x = (*x)-1;
- *y = (*y)+2;
- return 1;
- } break;
- case 1:if((*x)+1<=X-1 && (*y)+2<=Y-1 && chess[*x+1][*y+2]==0)
- {
- *x = (*x)+1;
- *y = (*y)+2;
- return 1;
- } break;
- case 2:if((*x)+2<=X-1 && (*y)+1<=Y-1 && chess[*x+2][*y+1]==0)
- {
- *x = (*x)+2;
- *y = (*y)+1;
- return 1;
- }break;
- case 3:if((*x)+2<=X-1 && (*y)-1>=0 && chess[*x+2][*y-1]==0)
- {
- *x = (*x)+2;
- *y = (*y)-1;
- return 1;
- } break;
- case 4:if((*x)+1<=X-1 && (*y)-2>=0 && chess[*x+1][*y-2]==0)
- {
- *x = (*x)+1;
- *y = (*y)-2;
- return 1;
- } break;
- case 5:if((*x)-1>=0 && (*y)-2>=0 && chess[*x-1][*y-2]==0)
- {
- *x = (*x)-1;
- *y = (*y)-2;
- return 1;
- } break;
- case 6:if((*x)-2>=0 && (*y)-1>=0 && chess[*x-2][*y-1]==0)
- {
- *x = (*x)-2;
- *y = (*y)-1;
- return 1;
- } break;
- case 7:if((*x)-2>=0 && (*y)+1<=Y-1 && chess[*x-2][*y+1]==0)
- {
- *x = (*x)-2;
- *y = (*y)+1;
- return 1;
- } break;
- default:break;
- }
- return 0;
- }
- #endif
- void print()
- {
- int i, j;
- for(i=0; i<X; i++)
- {
- for(j=0; j<Y; j++)
- {
- printf("%2d\t", chess[i][j]);
- }
- printf("\n");
- }
- }
- //深度优先遍历
- //(x,y)为位置坐标
- //tag是标识变量,每走一步tag+1
- int TravelChessBoard(int x, int y, int tag)
- {
- int x1, y1, flag, count;
- x1 = x;
- y1 = y;
- flag = count = 0;
- chess[x][y] = tag;
- //判断是否走完
- if(X*Y == tag)
- {
- print();
- return 1;
- }
- //判断下一步能不能走,能flag = 1
- flag = nextxy(&x1, &y1, count);
- while(0 == flag && count < 8)
- {
- count++;
- flag = nextxy(&x1, &y1, count);
- }
- while(flag)
- {
- if(TravelChessBoard(x1, y1, tag+1))
- return 1;
- //没找到下一个可以跳的,则回溯
- x1 = x;
- y1 = y;
- count++;
- flag = nextxy(&x1, &y1, count);
- while(0 == flag && count < 8)
- {
- count++;
- flag = nextxy(&x1, &y1, count);
- }
- }
- //这条路不通,还原标志
- if(0 == flag)
- chess[x1][y1] = 0;
- return 0;
- }
- int main()
- {
- int i, j;
- clock_t start, finish;
- start = clock();
- for(i=0; i<X; i++)
- {
- for(j=0; j<Y; j++)
- {
- chess[i][j]=0;
- }
- }
- if(!TravelChessBoard(2, 0, 1))
- printf("\nsorry,马踏棋盘失败!\n");
- finish = clock();
- printf("\n本次计算时间为%lf秒\n",(double)(finish-start)/CLOCKS_PER_SEC);
-
- system("pause");
- return 0;
- }
复制代码 |
|