文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C++骑士游历问题(马踏棋盘)解析

2024-04-02 19:55

关注

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

解题思路:

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

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

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

②设置标记

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

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  //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;
}

⑥测试截图:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程网。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯