C++骑士游历问题的示例分析
导读:本文共2504.5字符,通常情况下阅读需要8分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 骑士游历问题:在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍,对于任意给定的顶点,输出一条符合上述要求的路径解题思路:这是一道经典的遍历问题(DFS),由于题目要求遍历全部,那么肯定要做标记,因此立马想到DFS深度优先算法。具体思路如下:①了解国际象棋以及国际象棋骑士的走法国际象棋和中国象棋,大同小异,毕竟中国象棋是老祖先。国际象棋棋子放在格子中,中国象棋放在... ...
目录
(为您整理了一些要点),点击可以直达。骑士游历问题:在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍,对于任意给定的顶点,输出一条符合上述要求的路径
解题思路:
这是一道经典的遍历问题(DFS),由于题目要求遍历全部,那么肯定要做标记,因此立马想到DFS深度优先算法。具体思路如下:
①了解国际象棋以及国际象棋骑士的走法
国际象棋和中国象棋,大同小异,毕竟中国象棋是老祖先。国际象棋棋子放在格子中,中国象棋放在点上,且国际象棋有64个格子。国际象棋的骑士和中国象棋的马功能相当,都可以走八个方位。走法是走“日”字,或英文字母大写的“L”形:即先向左(或右)走1格,再向上(或下)走2格;或先向左(或右)走2格,再向上(或下)走1格。与中国象棋的馬不同,国际象棋的马可以跳过路上的其他棋子,不受拐脚的限制。
解题需要我们可以把格子抽象成一个点,那么国际象棋的骑士走法就是一个日字。
②设置标记
初始化数组,让每个元素初始化为0,并且初始化一个记录骑士遍历次数的cal也为0
intcal=0;//统计走的顺序//初始化为0intchress[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};
③判断是否超界和是否被访问
boolifOut(intx,inty)//判断是否出界{if(x>=0&&x<=7&&y>=0&&y<=7)returnfalse;elsereturntrue;}boolifVisited(intx,inty)//判断是否被访问{if(chress[x][y]!=0)returntrue;elsereturnfalse;}
④递归主体
voiddfs(intx,inty){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>usingnamespacestd;intcal=0;//统计走的顺序//棋盘初始化为0做标记intchress[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};boolifOut(intx,inty)//判断是否出界{if(x>=0&&x<=7&&y>=0&&y<=7)returnfalse;elsereturntrue;}boolifVisited(intx,inty)//判断是否已经被访问{if(chress[x][y]!=0)returntrue;elsereturnfalse;}voiddfs(intx,inty){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//出界了则退出returnreturn;}intmain(){intx,y;cout<<"请输入骑士初始的位置:";while(1){cin>>x>>y;//输入坐标if(x>7||x<0||y>7||y<0)cout<<"初始位置输入错误请重新输入"<<endl;elsebreak;}dfs(x,y);for(inti=0;i<8;i++)//输出打印测试{for(intj=0;j<8;j++)cout<<setw(2)<<chress[i][j]<<"";cout<<endl;}return0;}
⑥测试截图:
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
C++骑士游历问题的示例分析的详细内容,希望对您有所帮助,信息来源于网络。