搜索

递归1--小游戏

gecimao 发表于 2019-07-25 23:46 | 查看: | 回复:

  个人简介:本科:西南大学,专业第一,每年国奖,加拿大留学交换,建模(美赛二等奖,国赛特等奖)。喜欢挑战,酷爱难的东西。每日反思,已有7年。每天可工作学习15小时。可实现一切网站功能效果。QQ交流群:942327638。第一份工作:华东师大图书馆自动化部。第二份工作:香港教育大学MIT部门。 择苦则安,择做则乐(闲)。虚拟终究比不过真实精彩之万一。视频+总结;--

  博客+总结。大纲+实例快速学习法。教程不能只看,要练。以实践而学。对比学习。相同并进。

  应用场景:原问题复杂,但是可以划分成许多性质相同的子问题,子问题容易求解

  有一个w * h 个正方格子的矩形板,每个正方格子上可以有一张游戏卡片, 当然也可以没有,当下面的情况满足时,认为

  两个游戏卡片之间有一条路径相连:1、路径只包含水平或者竖直的直线、路径不能穿过别的游戏卡片;3、但是允许

  路径临时的离开矩形板。判断是否存在一条满足题意的路径能连接给定的两个游戏卡片。

  使用 X 表示这个地方有一个游戏卡片,使用空格 表示这个地方没有游戏卡片

  注意: 矩形板左上角的坐标是(1,1),输入保证这两个游戏卡片所处的位置是不相同的

  而在 (2,3) 和 (3,4) 处的游戏卡是不相连的, 因为连接它们的每条路径都必须要穿过别的游戏卡片。

  对每一个矩形板, 输出一行 “Board #n:”, n是输入数据的编号

  对每一组需要测试的游戏卡片输出一行. 这一行的开头是 “Pair m: ”,

  如果可以相连, 找到连接这两个卡片的所有路径中包括线段数最少的路径, 输出 “k segments.”

  如果不能相连, 输出 “impossible.”,每组数据之后输出一个空行。

  如果上一步走的方向和这一步走的方向相同, 递归搜索时路径数不变, 否则路径数加1

  路径只包含水平或者竖直的直线段. 路径不能穿过别的游戏卡片. 但是允许路径临时的离开矩形板

  2. 在搜索过程中, 用另外一个二维数mark[][]标记格子是否已经走过了

  2、这种长方形不要理解为x和y,理解为宽width和高height,而且直接把表格和坐标画出来,直观

  7、递归的边界条件是到达终点, 递归的递推公式就是上下左右走 ,只不过边界条件和递推公式都做了剪枝

  8、边界条件的剪枝是当前步数大于能成功的最小步数,所以当前这种情况应该勇敢舍去

  9、递推公式的剪枝是下一点在边界内,下一点可以走并且没有被走过,或者下一点是终点(这个条件好像可有可无)

  10、递归函数记录了关键的信息,当前点,下一点,步数和方向,因为我们要求的是步数,而方向决定步数

  11、如果是我,我会把对当前四边的扩展区域写在一起,当然,扩展边界这个思路特别好

  12、直接和一个二维数组相加表示东南西北,当然你之前要把这个图画出来,这个挺好的

本文链接:http://windsorflowers.net/diguilicheng/378.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部