骑士巡游问题 C/C++实现

本文主要是介绍骑士巡游问题 C/C++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

骑士游历问题：
在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍， 对于任意给定的顶点，输出一条符合上述要求的路径。骑士的走法和中国象棋的马的走法一样，走日。

二、解法思路

这道题骑士很容易就想到用DFS进行遍历，找到所有可以走的路径。用counter计入步数。用chess数组当作棋盘，没有走过则用0表示，走过则用当前步数表示。先判断自己当前可以走的位置，如果当前没有可走位置，则回溯到上一位置，寻找另一个可以继续走的位置。当走够了64次，也就是全部遍历，则完成。对于走的位置不能超过棋盘，不能被访问过。

三、代码

int chess[8][8] = {};
int counter = 0;
bool isOut(int x ,int y)//判断是否超过棋盘
{if(x>=0&&x<=7&&y>=0&&y<=7){return false;} else{return true;}
}bool isVisited(int x,int y)//判断是否被访问过{if(chess[x][y]!=0){return true;} else{return false;}}void dfs(int x,int y){if(counter == 64)return;if(!(isOut(x,y))&&!(isVisited(x,y))){counter++;chess[x][y] = counter;dfs(x+2,y+1);dfs(x+1,y+2);dfs(x-1,y+2);dfs(x-2,y+1);dfs(x-2,y-1);dfs(x-1,y-2);dfs(x+1,y-2);dfs(x+2,y-1);return;} else{return;}}

四、输出演示

这篇关于骑士巡游问题 C/C++实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---