百度站长工具数据提交,云南文投建设投资有限公司网站,wordpress断点续传,供货合同模板免费题目渊源#xff1a; 马踏棋盘问题#xff08;又称骑士周游问题或骑士漫游问题#xff09;是算法设计的经典问题之一。
题目要求#xff1a; 国际象棋的棋盘为8*8的方格棋盘#xff0c;现将“马”放在任意指定的方格中#xff0c;按照“马”走棋的规则将“马”进行移动。…题目渊源 马踏棋盘问题又称骑士周游问题或骑士漫游问题是算法设计的经典问题之一。
题目要求 国际象棋的棋盘为8*8的方格棋盘现将“马”放在任意指定的方格中按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次最终使得“马”走遍棋盘64个方格。 #include stdio.h
#include time.h#define X 8
#define Y 8int chess[X][Y];//找到基于xy位置的下一个可走的位置
int nextxy(int *x,int *y,int count)
{switch(count){case 0:if(*x2X-1 *y-10 chess[*x2][*y-1]0){*y2;*y-1;return 1;}break;case 1:if(*x2X-1 *y1Y-1 chess[*x2][*y1]0 ){*x2;*y1;return 1;}break;case 2:if(*x1X-1 *y-20 chess[*x1][*y-2]0 ){*x*x1;*y*y-2;return 1;}break;case 3:if(*x1X-1 *y2Y-1 chess[*x1][*y2]0){*x *x1;*y *y2;return 1;}break;case 4:if(*x-20 *y-10 chess[*x-2][*y-1]0){*x *x-2;*y *y1;return 1;}break;case 5:if(*x-20 *y1Y-1 chess[*x-2][*y1]0 ){*x *x-2;*y *y1;return 1;}break;case 6:if(*x-10 *y-20 chess[*x-1][*y-2]0){*x *x - 1;*y *y - 2;return 1;}break;case 7:if(*x-10 *y2Y-1 chess[*x-1][*y2]0){*x *x -1;*y *y 2;return 1;}break;default:break;} return 0;
} void print()
{int i,j;for(i0;iX;i){for(j0;jY;j){printf(%2d\t,chess[i][j]);}printf(\n);}printf(\n);
}//深度优先遍历棋盘
//xy为位置坐标
//tag是标记变量
int TravelChessBoard(int x,int y,int tag)
{int x1 x,y1y,count 0,flag 0;chess[x][y] tag;if(x*Y tag){//打印棋盘print();return 1; }//找到马的下一个可走的坐标x1y1flag nextxy(x1,y1,count);while(0flag count7){count;}while(flag){if(TravelChessBoard(x1,y1,tag1)){return 1;}//出现意外找到马的下一步可走坐标x1y1 x1x;y1y;count;flag nextxy(x1,y1,count);while(0flag count 7){count;flag nextxy(x1,y1,count);}} if(0 flag){chess[x][y] 0;} return 0;
} int main()
{int i,j;clock_t start,finish;start clock();for(i0;iX;i){for(j0;jY;j){chess[i][j]0;}}if(TravelChessBoard(2,0,1)){printf(抱歉马踏棋盘失败\n);}finish clock();printf(\n本次计算一共耗时:%f秒\n\n,(double)(finish - start)/CLOCKS_PER_SEC);return 0;
}
