目录前言马踏棋盘问题代码以及注释总结前言打怪升级第100天马踏棋盘问题【问题描述】设计一个国际象棋的马踏遍棋盘的演示程序。【基本要求】将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中马按走棋规则进行移动。要求每个方格只进入一次走遍棋盘上全部64个方格。编制非递归程序求出马的行走路线并按求出的行走路线将数字12…64依次填入一个8×8的方阵输出之。【涉及到的知识点】递归、回溯算法【题目分析】想要解决马踏棋盘问题首先要了解在象棋中马的行走方式马走日如下图所示解释可以先向上或向下走两格再向左或向右走一格也可以先向左或向右走两格再向上或向上走一格。也就是说马在移动的时候最多可以往八个方向走。由于每个位置只可以走一次我们就需要记录下这个位置是否已经走过了并且还需要记录该位置是第几次走过的我们在这里分别创建了两个二位数组分别记录该位置是否做过和是第几次走过的。解决了记录数据的问题下面需要解决的是马最多可以走8个位置我们怎么判断马应该走哪里呢这里我们对下一个位置next的选择方法为next可以走的路径越少我们就选它也就是说我们在选next的时候需要先判断next的next有几种情况并对这几种情况进行排序选出可走路径最少的情况一条路走到黑。这里我们在选择next的时候不仅要知道它的xy下标还需要知道它的可走路径数量由于内容较多我们为它创建一个结构体。这里我们不能只创建三个变量来选择最小的因为如果则条路走不通我们需要回溯回来选择另一条路如果不把结果都保存下来等到回溯的时候还需要重复之前的选择遍历了解本问题所涉及的递归和迭代算法递归我们平时所说的函数自己调用自己就是递归这时需要一个特定的结束条件这里是 马走过的方格数 64 或者 无路可走。我们这里使用的是dfs算法既深度优先遍历换句话说就是我们跳到一个方格就顺着这个方格继续往后跳此时的函数层层压栈直到达到结束条件时才开始出栈。迭代从某个值开始不断由上一步的结果计算或推断出下一步的结果就叫迭代换句话说就是递归函数不断递归不断靠近结束条件的过程由于每一次移动都需要确定下一位置的可以走的最少路径需要嵌套非常非常多的for循环而这里我们就将此过程交给了递归函数去判断。代码以及注释#define_CRT_SECURE_NO_WARNINGS1#includeiostream#includevector#includestringusingnamespacestd;typedefstructLocation{intcurx;intcury;intcon;// 可走路径}Location;introw0;// 棋盘大小intcol0;vectorstringchessboard;// 记录棋盘位置 是否走过vectorvectorintrecord;// 记录该位置是 第几次走过的intsum0;// 记录走过的格数intrmove[8]{1,1,-1,-1,2,2,-2,-2};// 1 - 行数1 表示向下走一格intcmove[8]{2,-2,2,-2,1,-1,1,-1};// 2 - 列数2 表示向右走两格voidShowChessboard()// 打印出每个位置走过的时机{for(inti0;irow;i){for(intj0;jcol;j){printf(%4d,record[i][j]);}printf(\n);}}boolVolid(intpos,intborder){returnpos0posborder;}// 判断 0 pos borderboolOrder(intx,inty)// 当前马所在的位置{if(row*colsum)// 1. 所以位置都走过了{returntrue;}Location*nextroute(Location*)calloc(8,sizeof(Location));// 记录下一个可走intr0;// 记录实际可走节点个数for(inti0;i8;i)// 最多可走8个位置 2. 没走完继续走{intnextxxrmove[i];// 可走的节点intnextyycmove[i];if(Volid(nextx,row)Volid(nexty,col)chessboard[nextx][nexty]0)// 该位置存在并且还未走过{nextroute[r].curxnextx;// 记录位置下面记录可走位置个数nextroute[r].curynexty;intcon0;// 统计可走位置个数for(intj0;j8;j)// next位置最多有8个位置可走记录可走位置个数{intnnextxnextxrmove[j];intnnextynextycmove[j];if(Volid(nnextx,row)Volid(nnexty,col)chessboard[nnextx][nnexty]0)// 该位置存在并且还未走过con;}nextroute[r].concon;r;}}if(r0)// 如果没有可走位置就退出并且回到本位置的上一个位置 2.1 这个位置是死路退回去重新走{sum--;// 退回去chessboard[x][y]0;// 该位置设为未走过record[x][y]0;// 设为未走过 - 第0次走过delete[]nextroute;returnfalse;}// 排序找到可走位置最少的节点先走 2.2 该位置可以往下走qsort(nextroute,r,sizeof(Location),[](constvoid*e1,constvoid*e2){return((Location*)e1)-con-((Location*)e2)-con;});for(inti0;ir;i){intnextxnextroute[i].curx;intnextynextroute[i].cury;sum;chessboard[nextx][nexty]1;record[nextx][nexty]sum;if(Order(nextx,nexty))// 为真说明棋盘遍历结束了{delete[]nextroute;returntrue;}// 否则说明走到了死路退回来遍历下一个节点}delete[]nextroute;returnfalse;// 遍历到最后也没走完表明从该位置不能遍历完棋盘}voidInit(intx,inty){cout请输入棋盘大小: row*col --;scanf(%d*%d,row,col);sum0;chessboard.clear();chessboard.assign(row,string(col,0));record.clear();record.assign(row,vectorint(col,0));cout请输入初始位置: x,y -- ;do{scanf(%d,%d,x,y);if(x0xrowy0ycol)break;elsecout坐标输入错误请重新输入endl;}while(1);x--;// 此时代表下标y--;}voidRun(){// 初始化棋盘并且获取初始位置intx,y;Init(x,y);// 开始周游if(Order(x,y))// 走完了棋盘就打印每个位置走过的时机{ShowChessboard();}else// 否则就提示无法走完{cout无法走完棋盘endl;}}intmain(){while(true){Run();}return0;}【运行实例】总结
【回溯 -- 马踏棋盘/骑士周游 】
目录前言马踏棋盘问题代码以及注释总结前言打怪升级第100天马踏棋盘问题【问题描述】设计一个国际象棋的马踏遍棋盘的演示程序。【基本要求】将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中马按走棋规则进行移动。要求每个方格只进入一次走遍棋盘上全部64个方格。编制非递归程序求出马的行走路线并按求出的行走路线将数字12…64依次填入一个8×8的方阵输出之。【涉及到的知识点】递归、回溯算法【题目分析】想要解决马踏棋盘问题首先要了解在象棋中马的行走方式马走日如下图所示解释可以先向上或向下走两格再向左或向右走一格也可以先向左或向右走两格再向上或向上走一格。也就是说马在移动的时候最多可以往八个方向走。由于每个位置只可以走一次我们就需要记录下这个位置是否已经走过了并且还需要记录该位置是第几次走过的我们在这里分别创建了两个二位数组分别记录该位置是否做过和是第几次走过的。解决了记录数据的问题下面需要解决的是马最多可以走8个位置我们怎么判断马应该走哪里呢这里我们对下一个位置next的选择方法为next可以走的路径越少我们就选它也就是说我们在选next的时候需要先判断next的next有几种情况并对这几种情况进行排序选出可走路径最少的情况一条路走到黑。这里我们在选择next的时候不仅要知道它的xy下标还需要知道它的可走路径数量由于内容较多我们为它创建一个结构体。这里我们不能只创建三个变量来选择最小的因为如果则条路走不通我们需要回溯回来选择另一条路如果不把结果都保存下来等到回溯的时候还需要重复之前的选择遍历了解本问题所涉及的递归和迭代算法递归我们平时所说的函数自己调用自己就是递归这时需要一个特定的结束条件这里是 马走过的方格数 64 或者 无路可走。我们这里使用的是dfs算法既深度优先遍历换句话说就是我们跳到一个方格就顺着这个方格继续往后跳此时的函数层层压栈直到达到结束条件时才开始出栈。迭代从某个值开始不断由上一步的结果计算或推断出下一步的结果就叫迭代换句话说就是递归函数不断递归不断靠近结束条件的过程由于每一次移动都需要确定下一位置的可以走的最少路径需要嵌套非常非常多的for循环而这里我们就将此过程交给了递归函数去判断。代码以及注释#define_CRT_SECURE_NO_WARNINGS1#includeiostream#includevector#includestringusingnamespacestd;typedefstructLocation{intcurx;intcury;intcon;// 可走路径}Location;introw0;// 棋盘大小intcol0;vectorstringchessboard;// 记录棋盘位置 是否走过vectorvectorintrecord;// 记录该位置是 第几次走过的intsum0;// 记录走过的格数intrmove[8]{1,1,-1,-1,2,2,-2,-2};// 1 - 行数1 表示向下走一格intcmove[8]{2,-2,2,-2,1,-1,1,-1};// 2 - 列数2 表示向右走两格voidShowChessboard()// 打印出每个位置走过的时机{for(inti0;irow;i){for(intj0;jcol;j){printf(%4d,record[i][j]);}printf(\n);}}boolVolid(intpos,intborder){returnpos0posborder;}// 判断 0 pos borderboolOrder(intx,inty)// 当前马所在的位置{if(row*colsum)// 1. 所以位置都走过了{returntrue;}Location*nextroute(Location*)calloc(8,sizeof(Location));// 记录下一个可走intr0;// 记录实际可走节点个数for(inti0;i8;i)// 最多可走8个位置 2. 没走完继续走{intnextxxrmove[i];// 可走的节点intnextyycmove[i];if(Volid(nextx,row)Volid(nexty,col)chessboard[nextx][nexty]0)// 该位置存在并且还未走过{nextroute[r].curxnextx;// 记录位置下面记录可走位置个数nextroute[r].curynexty;intcon0;// 统计可走位置个数for(intj0;j8;j)// next位置最多有8个位置可走记录可走位置个数{intnnextxnextxrmove[j];intnnextynextycmove[j];if(Volid(nnextx,row)Volid(nnexty,col)chessboard[nnextx][nnexty]0)// 该位置存在并且还未走过con;}nextroute[r].concon;r;}}if(r0)// 如果没有可走位置就退出并且回到本位置的上一个位置 2.1 这个位置是死路退回去重新走{sum--;// 退回去chessboard[x][y]0;// 该位置设为未走过record[x][y]0;// 设为未走过 - 第0次走过delete[]nextroute;returnfalse;}// 排序找到可走位置最少的节点先走 2.2 该位置可以往下走qsort(nextroute,r,sizeof(Location),[](constvoid*e1,constvoid*e2){return((Location*)e1)-con-((Location*)e2)-con;});for(inti0;ir;i){intnextxnextroute[i].curx;intnextynextroute[i].cury;sum;chessboard[nextx][nexty]1;record[nextx][nexty]sum;if(Order(nextx,nexty))// 为真说明棋盘遍历结束了{delete[]nextroute;returntrue;}// 否则说明走到了死路退回来遍历下一个节点}delete[]nextroute;returnfalse;// 遍历到最后也没走完表明从该位置不能遍历完棋盘}voidInit(intx,inty){cout请输入棋盘大小: row*col --;scanf(%d*%d,row,col);sum0;chessboard.clear();chessboard.assign(row,string(col,0));record.clear();record.assign(row,vectorint(col,0));cout请输入初始位置: x,y -- ;do{scanf(%d,%d,x,y);if(x0xrowy0ycol)break;elsecout坐标输入错误请重新输入endl;}while(1);x--;// 此时代表下标y--;}voidRun(){// 初始化棋盘并且获取初始位置intx,y;Init(x,y);// 开始周游if(Order(x,y))// 走完了棋盘就打印每个位置走过的时机{ShowChessboard();}else// 否则就提示无法走完{cout无法走完棋盘endl;}}intmain(){while(true){Run();}return0;}【运行实例】总结
