|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- #include <stdio.h>
- #include <stdlib.h>
- #define X 8
- #define Y 8
- typedef struct step{
- int x;
- int y;
- int door;
- } step;
- int chessboard[Y][X]; // 建立一个棋盘
- step footprint[Y*X+1]; // 记录曾经走过的每一步
- int stepNum; // 走过的步数
- void push(int x, int y, int door)
- {
- footprint[stepNum].x = x;
- footprint[stepNum].y = y;
- footprint[stepNum].door = door;
- stepNum++;
- }
- void pop(int *x, int *y, int *door)
- {
- stepNum--;
- *x = footprint[stepNum].x;
- *y = footprint[stepNum].y;
- *door = footprint[stepNum].door;
- }
- int test(int *x, int *y, int door)
- {
- switch(door)
- {
- case 0:
- if((*x-1)>=0 && (*y-2)>=0 && chessboard[*y-2][*x-1]==0)
- {
- *x-=1;
- *y-=2;
- return 1;
- }
- break;
- case 1:
- if((*x+1)<X && (*y-2)>=0 && chessboard[*y-2][*x+1]==0)
- {
- *x+=1;
- *y-=2;
- return 1;
- }
- break;
- case 2:
- if((*x+2)<X && (*y-1)>=0 && chessboard[*y-1][*x+2]==0)
- {
- *x+=2;
- *y-=1;
- return 1;
- }
- break;
- case 3:
- if((*x+2)<X && (*y+1)<Y && chessboard[*y+1][*x+2]==0)
- {
- *x+=2;
- *y+=1;
- return 1;
- }
- break;
- case 4:
- if((*x+1)<X && (*y+2)<Y && chessboard[*y+2][*x+1]==0)
- {
- *x+=1;
- *y+=2;
- return 1;
- }
- break;
- case 5:
- if((*x-1)>=0 && (*y+2)<Y && chessboard[*y+2][*x-1]==0)
- {
- *x-=1;
- *y+=2;
- return 1;
- }
- break;
- case 6:
- if((*x-2)>=0 && (*y+1)<Y && chessboard[*y+1][*x-2]==0)
- {
- *x-=2;
- *y+=1;
- return 1;
- }
- break;
- case 7:
- if((*x-2)>=0 && (*y-1)>= 0 && chessboard[*y-1][*x-2]==0)
- {
- *x-=2;
- *y-=1;
- return 1;
- }
- break;
- default :
- break;
- }
- return 0;
- }
- void print_chessboard()
- {
- int i, j;
- printf("\n");
- for(i = 0; i < Y; i++)
- {
- for(j = 0; j < X; j++)
- {
- printf("%02d ",chessboard[i][j]);
- }
- printf("\n");
- }
- }
- int travel(int x, int y)
- {
- int i = 0;
- int x2, y2;
- while(1){
- // 建立x y 的副本
- x2 = x;
- y2 = y;
- // 为走过的点写上标号
- printf("%d\n", stepNum);
- chessboard[y][x] = stepNum + 1;
- // 寻找可落脚点
- for(; i < 8; i++) // 落脚点只有8个,依次寻找
- {
- if(test(&x2, &y2, i))
- {
- if(stepNum == (Y*X-2)) // 如果已将完成 全部点的寻找 则直接打印棋盘 并退出
- {
- print_chessboard();
- return 1;
- }
- push(x, y, i); // 将走过的点 推入栈中
- // 设置 下一个可走点 为当前点
- x = x2;
- y = y2;
- i = 0; // 下一个点 从第一个点开始测试
- break; // 找到落脚点 退出循环
- }
- }
- // 所有落脚点均不可落脚,弹出上次落脚点,从上一次落脚点继续寻找
- if(i == 8) // 如果i自增到啦8,就是说没有找到下一个落脚点
- {
- if(stepNum == 0) // 如果没有找到 符合要求的棋盘路径则 返回0
- {
- return 0;
- }
- chessboard[y][x] = 0; // 退回时将走错的 归0
- pop(&x, &y, &i); // 将上一步弹出 并还原
- i++; // 从上一步测试的 下一个点继续测试
- }
- }
- return 0; // 如果没有找到 符合要求的棋盘路径则 返回0
- }
- int main()
- {
- if(travel(2, 0) == 0 )
- {
- printf("没有找到\n");
- }
- return 0;
- }
复制代码 我弄啦快两天,实在是搞不定啦,到底是我机器慢,还是我写成死循环啦?
|
|