- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
8600骑士问题
8600?骑士问题时间限制:1000MS? 内存限制:1000K提交次数:0 通过次数:0题型: 编程题???语言: 无限制Description在一个标准8×8的国际象棋棋盘上,棋盘中有些格子是可能有障碍物的。已知骑士的初始位置和目标位置,你的任务是计算出骑士最少需要多少步可以从初始位置到达目标位置。有障碍物的格子当然不可能到达。标准的8×8的国际象棋棋盘中每一个格子可以用唯一的编号确定。行用1~8这8个数字依次表示,列用“a”~“h”这8个字母依次表示。例如下图(a)的骑士所在位置(图中有n的格子)的编号为“d4”(注意“d”和“4”之间没有空格)。 我们知道国际象棋中的骑士可以按“L”路线移动(一个方向走2个格子,接着垂直方向走一个格子)。因此,如图(a)所示的骑士(位于d4),可以到达位置c2,b3,b5,c6,e6,f5,f3和e2(图中有“x”标记的格子)。此外,骑士不能移出棋盘。骑士可以按照移动规则自由地在棋盘上没有障碍物的格子中移动。图(b)给出了一个骑士移动的例子,也就是输入样例中第一组数据对应的例子。初始格子用“n”标记,目标格子用“N”标记,有障碍物的格子用“b”标记。一个可行的移动序列在图中用数字标记出来(a1,b3,a5,c6,e5,g4,h2,f1)。总共需要7步才能完成。事实上,这也是最少的步数了。 Input输入包含1个或多个测试数据。每一个测试数据的第一行是一个整数b(-1 = b = 62),表示棋盘中有障碍物的格子数目。当b=-1时,输入结束。第二行含b个不同的障碍物的格子编号,用空格隔开。当b=0时,此行为空行。第三行是骑士的初始格子和目标格子的编号,也是用空格隔开。初始格子和目标格子是不同的,且都没有障碍物。Output对于每个数据,输出一行。格式Board n:m moves其中n表示数据的序号(从1开始),m表示骑士所用的最小步数。如果骑士无法到达目标格子,输出Board n:not reachableSample Input10c1 d1 d5 c2 c3 c4 d2 d3 d4 c5a1 f10c1 b32b3 c2a1 b2-1Sample OutputBoard 1:7 movesBoard 2:1 movesBoard 3:not reachableHint这也是一个有哪些信誉好的足球投注网站的题目,非常类似于书上的“布线问题”,解法几乎同,可参考书上此范例。用一个二维数组board[12][12]来记录棋盘的状况。为何大小是12*12呢?棋盘大小8*8,为了减少对周围边界的判断,在上下左右四边各加上2行2列做“围墙”(障碍),因此board棋盘的大小12*12。有如下几个问题或步骤需要解决:1,障碍格子:将输入的障碍格子填写到board当中对应格上,设置为-1;2,起始格子和结束格子:将起始点start和结束点end,这两个点记录下来,在board中这两个格子设置为0;3,围墙:在8*8的棋盘外面,上下左右各加2行2列做围墙,围墙和障碍一样,设置为-1;4,除障碍、围墙、起始、结束格子这些格子特殊对待之外,其余格子全部初始化为0;5,队列初始为空。队列是用来在骑士做 “日字型”对角跳的时候,候选位置放入队列中的一个辅助的数据结构,以便于“广度优先有哪些信誉好的足球投注网站”。6,从起点开始,将这个位置所能跳的周围8个位置都检查一下:只要未标记,就标记为前一个位置值加1,并将该位置入队列;如果不能标记(比如障碍或围墙等),就跳过,继续检查下一个位置,一共八个骑士所能跳的位置。7,取出队列首个位置结点,又继续检查这个结点周围的8个位置,类同上一步,直到找到对终点标记位置。8,最后,输出终点所标记的数值(正数),就是骑士所需的最少移动步数,若为0表示终点无法标记到,输出:“not reachable”这样的信息。1--5为初始化步骤,在标记之前就应该做好棋盘和相关辅助数据结构的初始化;6--8为标记过程。ProviderzhengchanSource Code#include iostream#include string.h #include queue #define N 70 using namespace std; bool g[N][N];int b;intstart,end; struct node{ intn,r,c,k; };queuestruct node q; int BFS() { intans,i,k,R[10],C[10],FIND;struct node tmp; while(!q.empty()) q.pop(); tmp.n=start; tmp.r=(start%8)==0 ? start/8 : start/8+1; tmp.c=(start%8)==0 ? 8: start%8;
您可能关注的文档
- 3-顾客与市场.doc
- 60授课计划(web前端开发).doc
- 4连续时间信号与系统的复频域分析.doc
- 5第五章电子商务安全.doc
- 52反比例函数.docx
- 2800mm冷轧机速度和张力控制.docx
- 6强夯施工工艺工法.doc
- 6仪表专业表格.doc
- 6第六章物理教学的艺术.doc
- 6动力学应用问题.doc
- 中国国家标准 GB/T 18233.4-2024信息技术 用户建筑群通用布缆 第4部分:住宅.pdf
- GB/T 18233.4-2024信息技术 用户建筑群通用布缆 第4部分:住宅.pdf
- GB/T 18978.210-2024人-系统交互工效学 第210部分:以人为中心的交互系统设计.pdf
- 《GB/T 18978.210-2024人-系统交互工效学 第210部分:以人为中心的交互系统设计》.pdf
- 中国国家标准 GB/T 18978.210-2024人-系统交互工效学 第210部分:以人为中心的交互系统设计.pdf
- GB/T 16649.2-2024识别卡 集成电路卡 第2部分:带触点的卡 触点的尺寸和位置.pdf
- 《GB/T 16649.2-2024识别卡 集成电路卡 第2部分:带触点的卡 触点的尺寸和位置》.pdf
- 中国国家标准 GB/T 16649.2-2024识别卡 集成电路卡 第2部分:带触点的卡 触点的尺寸和位置.pdf
- GB/T 17889.4-2024梯子 第4部分:铰链梯.pdf
- 《GB/T 17889.4-2024梯子 第4部分:铰链梯》.pdf
最近下载
- 百日咳试题附有答案.docx VIP
- 2024年广东省深圳市光明区人大常委会办公室招聘一般类岗位专干12人历年【综合基础知识500题】高频考点模拟试题及参考答案解析.docx VIP
- 高中语文任务驱动型材料作文:枯燥与热闹审题指导(含解析).docx VIP
- 某镇卫生院污水设计方案.pdf VIP
- 2024年广东深圳市光明区人大常委会办公室招聘一般类岗位专干3人历年【综合基础知识500题】高频考点模拟试题及参考答案解析.docx VIP
- 中考数学经验交流会发言稿.pdf
- 2024年7月广东省深圳市光明区人大常委会办公室招聘10人历年【高频考点汇总500题】模拟卷及参考答案详解.docx VIP
- 《溜冰圆舞曲和雷鸣电闪波尔卡》精品课件2023.pptx
- 水利项目安全评价报告.docx
- 2024年7月广东省深圳市光明区人大常委会办公室招聘10人历年【综合基础知识500题】高频考点模拟试题及参考答案解析.docx VIP
文档评论(0)