C++骑士游历问题的示例分析

这篇文章主要介绍了C++骑士游历问题的示例分析，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

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

解题思路：

这是一道经典的遍历问题（DFS），由于题目要求遍历全部，那么肯定要做标记，因此立马想到DFS深度优先算法。具体思路如下：

①了解国际象棋以及国际象棋骑士的走法

国际象棋和中国象棋，大同小异，毕竟中国象棋是老祖先。国际象棋棋子放在格子中，中国象棋放在点上，且国际象棋有64个格子。国际象棋的骑士和中国象棋的马功能相当，都可以走八个方位。走法是走“日”字，或英文字母大写的“L”形：即先向左（或右）走1格，再向上（或下）走2格；或先向左（或右）走2格，再向上（或下）走1格。与中国象棋的馬不同，国际象棋的马可以跳过路上的其他棋子，不受拐脚的限制。
解题需要我们可以把格子抽象成一个点，那么国际象棋的骑士走法就是一个日字。

②设置标记

初始化数组，让每个元素初始化为0，并且初始化一个记录骑士遍历次数的cal也为0

int cal = 0; //统计走的顺序//初始化为0int chress[8][8] =           {    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0};

③判断是否超界和是否被访问

bool ifOut(int x, int y)  //判断是否出界{    if (x >= 0 && x <= 7 && y >= 0 && y <= 7)        return false;    else        return true;}bool ifVisited(int x, int y) //判断是否被访问{    if (chress[x][y] != 0)        return true;    else        return false;}

④递归主体

void dfs(int x,int y){        if (cal == 64) //如果遍历完则退出棋盘一共64个位置        return;    if (!ifVisited(x, y) && !ifOut(x, y)) //如果没有被访问且没有出界 则访问    {        cal++;           chress[x][y] = cal; //做标记        dfs(x + 2, y + 1);    //骑士走法有八个方位，故八个 方位都遍历        dfs(x - 2, y - 1);   //八个递归的顺序可以改，顺序不一样，结果不一样        dfs(x + 2, y - 1);            dfs(x - 2, y + 1);            dfs(x - 1, y - 2);          dfs(x + 1, y - 2);            dfs(x + 1, y + 2);            dfs(x - 1, y + 2);          return;    }    else  //else其中包括已经被访问了，和没有被访问且在界外的        return;}

⑤总代码如下（编译器vs2013）

#include"stdafx.h"#include<iostream>#include<iomanip>using namespace std;int cal = 0; //统计走的顺序//棋盘初始化为0做标记int chress[8][8] =           {    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0,    0, 0, 0, 0, 0, 0, 0, 0};bool ifOut(int x, int y)  //判断是否出界{    if (x >= 0 && x <= 7 && y >= 0 && y <= 7)        return false;    else        return true;}bool ifVisited(int x, int y) //判断是否已经被访问{    if (chress[x][y] != 0)        return true;    else        return false;}void dfs(int x,int y){        if (cal == 64) //如果遍历完则退出棋盘一共64个位置        return;    if (!ifVisited(x, y) && !ifOut(x, y)) //如果没有被访问且没有出界 则访问    {        cal++;           chress[x][y] = cal; //做标记        dfs(x + 2, y + 1);    //骑士走法有八个方位，故八个 方位都遍历        dfs(x - 2, y - 1);  //八个递归的顺序可以改，顺序不一样，结果不一样         dfs(x + 2, y - 1);            dfs(x - 2, y + 1);            dfs(x - 1, y - 2);          dfs(x + 1, y - 2);            dfs(x + 1, y + 2);            dfs(x - 1, y + 2);          return;    }    else  //出界了则退出return        return;}int main(){        int x, y;    cout << "请输入骑士初始的位置：";    while (1)    {        cin >> x >> y;    //输入坐标        if (x > 7 || x<0 || y> 7 || y < 0)            cout << "初始位置输入错误请重新输入" << endl;        else            break;    }    dfs(x,y);    for (int i = 0; i < 8; i++)  //输出打印测试    {        for (int j = 0; j < 8; j++)            cout << setw(2)<<chress[i][j]<<"  ";        cout << endl;    }    return 0;}

⑥测试截图：

感谢你能够认真阅读完这篇文章，希望小编分享的“C++骑士游历问题的示例分析”这篇文章对大家有帮助，同时也希望大家多多支持编程网，关注编程网行业资讯频道，更多相关知识等着你来学习!