展开

关键词

蓝桥杯-python算法

问题描述 下图给出了一个的平面图,其中标记为 1 的为障碍,标记为 0 的为可 以通行的地方。 ? 的入口为左上角,出口为右下角,在中,只能从一个位置到这个它的上、下、左、右四个方向之一。 对于上面的,从入口开始,可以按DRRURRDDDR 的顺序通过, 一共 10 步。 其中 D、U、L、R 分别表示向下、向上、向左、向右。 我们写出一个算法来计算不同时的最优路径。 解决方案 首先先清楚我们要的实质就是一个矩阵,即用(x,y)即可表示内的任意一点,再用一个字符串w来表示路径。 self.x = x self.y = y self.w = w def __str__(self): return self.w 定义好节点后我们再想一想怎么在里进行移动

1.1K30

C++

用20x20的方形区域作为,为了方便,随机选取了大约1/3的格子作为路障,禁止通过。规则是在只能想前后左右四个方向移动的前提下找到从入口(默认左上角)到出口(默认右下角)的最短路径。 界面很简单,进入程序或者点击建立时生成一个随机,点击寻找路径后电脑会执行寻路算法,通过提示框提示寻路是否成功及迭代次数,如果成功显示路径和每个格子到出口的距离。 下面的两组图片是生成的和找到的路径,运行时间没有计算,人工观测都小于1秒。有兴趣的筒子可以验证一下是不是最短的路径。 寻路的核心代码如下: 数据用的是“vector<Block *> _blocks”按照行优先的格式存下来的,在之前生成的时候就已经控制了入口和出口不是障碍,所以一开始先把出口的位置数据初始化了一下 括号有十层,确实有点晕了,事实上不建议这样写代码的,超过五层括号就让人很惑了。但是考虑到程序本身比较小,既是不拆分函数也只有50行,不算变态(有一次需要读懂一个700行的函数,泪奔啊!!)

8620
  • 广告
    关闭

    腾讯云618采购季来袭!

    一键领取预热专享618元代金券,2核2G云服务器爆品秒杀低至18元!云产品首单低0.8折起,企业用户购买域名1元起…

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    蚂蚁

    01 故事起源 有一只蚂蚁出去寻找食物,无意中进入了一个。蚂蚁只能向上、下、左、右4个方向中有墙和水的地方都无法通行。这时蚂蚁犯难了,怎样才能找出到食物的最短路径呢? ? 当然要排除之前过的地方(不回头路,了也只会更长)和无法通过的墙和水。 ? 蚂蚁想,还好我会影分身。 如果每一步都分身成4个蚂蚁,向4个方向各1步,这样最先找到食物的肯定就是最短的路径了(因为每一步都把能的地方都完了,肯定找不出更短的路径了)。 ? 03 问题建模 把地图放在二维数组中,能通行的地方为0,墙和水的地方为负数。 ? 每一步向4个方向,可以通过当前坐标加上一个方向向量。 ? 这个其实就是宽度优先搜索(BFS)的思想。 回归问题,到起点的距离为1,2,3...的点会依次入队。 ? 当head指针遍历到距离为2的点时,向4周扩展距离为3的节点,并继续入队。 ?

    42250

    用栈、回溯算法设计程序

    目录 1、与回溯算法 2、设计栈扮演的角色 3、Python实现 ---- 栈的应用有许多,本篇博文着重将栈与回溯(Backtracking)算法结合,设计程序。 1、与回溯算法 假设一个简单的图形如下图所示: ? 一个基本上由4种空格组成: 入口:的入口,笔者上图用绿色表示。 通道:的通道,笔者上图用黄色表示。 墙壁:的墙壁,不可通行,笔者上图用灰色表示。 出口:的出口,笔者上图用蓝色表示。 在时,可以上、下、左、右行,如下图所示: ? 时每次可以一步,如果碰到墙壁不能穿越必须其他方向。 第1步:假设目前位置在入口处,可以参考下图所示: ? 3、Python实现 使用Python设计可以使用二维的列表,0代表通道、1代表墙壁,至于起点和终点也可以用0代表。

    27530

    Python 算法实战系列:栈

    题目 用一个二维数组表示一个简单的,用0表示通路,用1表示阻断,老鼠在每个点上可以移动相邻的东南西北四个点,设计一个算法,模拟老鼠,找到从入口到出口的一条路径。 /use/bin/env python # _*_ coding:utf-8 _*_ def initMaze(): """ :return: 初始化 """ maze = [[ (2, 5), (3, 3), (3, 4), (4, 2), # (4, 3), # 如果把(4, 3)点也设置为墙,那么整个不出去的,所以会返回一个空列表 (5, 4) ] for stack.pop() # 退回上一步 return stack # 如果不能则返回空栈 Maze = initMaze() # 初始化 result = path(maze=Maze, start=(1, 1), end=(5, 5)) # 老鼠开始 print(result) # [(1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1),

    48780

    【算法】老鼠

    老鼠官(一) 说明老鼠是递回求解的基本题型,我们在二维阵列中使用2表示墙壁,使用1来表 示老鼠的行路径,试以程式求出由入口至出口的路径。 解法老鼠的法有上、左、下、右四个方向,在每前进一格之后就选一个方向前进,无法前 进时退回选择下一个可前进方向,如此在阵列中依序测试四个方向,直到到出口为止,这是 递回的基本题,请直接看程式应就可以理解 入口 int endI = 5, endJ = 5; // 出口 int success = 0; int main(void) { int i, j; printf("显示 = 1) maze[i][j] =0; return success; } 老鼠官(二) 说明由于的设计, 老鼠的入口至出口路径可能不只一条 1, startJ = 1; // 入口 int endI = 7, endJ = 7; // 出口 int main(void) { int i, j; printf("显示

    538110

    (bfs, 最短路)

    39620

    Python妙用】用200行Python代码制作一个小游戏

    相信大家都玩过的游戏,对于简单的,我们可以一眼就看出通路,但是对于复杂的,可能要仔细寻找好久,甚至耗费数天,然后可能还要分别从入口和出口两头寻找才能找的到通路,甚至也可能找不到通路。 虽然问题对于我们人类来讲比较复杂,但对于计算机来说却是很简单的问题。为什么这样说呢,因为看似复杂实则是有规可循的。 上面这种的算法就是我们常说的深度优先遍历算法,与之相对的是广度优先遍历算法。有了理论基础,下面我们就来试着用 程序来实现一个的小程序。 生成 生成有很多种算法,常用的有递归回溯法、递归分割法和随机 Prim 算法,我们今天是用的最后一种算法。 得到了的地图,接下来就按照我们文首的思路来即可。

    90330

    重学数据结构之队列

    使用 Python 实现一个优先级队列,可以借助 Python 中的 heapq 模块来实现,heapq 是一个二叉堆的实现,其内部使用内置的 list 对象,对于列表中的每一个元素都满足 a[k] < 1)问题描述 将一个映射成一个由0和1组成的二维矩阵,里的空位置用0来表示,障碍和边界用1来表示,最左上角为入口,最右下角为出口,求是否能从出来? 将中已经过的位置进行标记,设置为2 4 :param maze: 5 :param pos: 位置 6 :return: 7 """ 8 maze[pos[0]][pos[1]] = 2 9 10 11 def passable(maze, pos): 12 """ 13 检车中指定位置是否能 14 : 对于每一个位置,都有如下的算法过程: 标记当前位置; 检查当前位置是否为出口,如果则表明找到路径,算法结束,不是则进行下一步; 遍历该位置的相邻位置,使用递归调用自身; 如果相邻位置都不可行,表明无法从出来

    16500

    Data Structure_Visualization排序可视化生成扫雷

    显示 生成等等再提,先看一下的读取和显示。 ? 第一行是行数和列数,代表有101行101列,这个后面可以使用最小生成树生成。 问题 白色方块是可以的路径,红色的就是墙。的本质就是一个图结构。可以把整个当成是一个图,而的过程就可以等价成是图的遍历。从起始点开始遍历,直到遍历到了某一个终止点即可。 首先固定了每一个的出口和入口位置,从一开始,就需要从相邻的四个方向,如果可以就继续,不能就回头,其实就是递归实现。 生成 刚刚是,刚刚生成的那个用例其实就是生成的。对于一个,只有一个入口一个出口,为了简单化,入口就是第二行的第一个口,出口是倒数第二行的第一个口。 但是其实还有一个问题,很多时候这个的路径顺序是都是斜向下的趋势,所以有时候是可以猜到怎么的。

    28930

    机器学习|用Q-Learning

    再回到我们今天要讲的例子上来,和下棋的原理其实类似,我们要的路无非就是两种:顺畅的路和有障碍的路,那我们要做的事也就很明了了,当触碰到障碍的时候给予一定的惩罚,了正确的路时给予一定的奖励,这样经过不断的训练 ,机器就应该能够知道该如何”“了。 我们要示意图如下: ? ? 02 代码实现 构建画布 ? 我们首先要做的就是来构建画布并且画出Python中Tkinter就是一个很好的画图工具(相对于其他的库来说,该库运行快,且不容易卡死) 构建画布的时候,我们除了需要构建基本的图形和,还需要实现行动的方式 ,对于简单的来说,我们只需要设定“上下左右”的行动方式就可以了,如果到了黑块就得到-1的惩罚并结束回合,到黄块得到1的奖励并结束回合。

    82430

    做题总结——

    做题总结—— 原题链接: 题目 ? { cin>>mp[i][j]; if(mp[i][j]=='S') { x.push(i); //将起点的坐标位置压入队列中

    22020

    每日一题 C++版(

    题目描述 定义一个二维数组N*M(其中2<=N<=10;2<=M<=10),如5 × 5数组下所示: int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个,其中的1表示墙壁, 入口点为[0,0],既第一空格是可以的路。 Input 一个N × M的二维数组,表示一个。输入两个整数,分别表示二位数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以的路。 数据保证有唯一解,不考虑有多解的情况,即只有一条通道。 Output 左上角到右下角的最短路径,格式如样例所示。 <vector<int>> maze;//矩阵 vector<vector<int>> path_temp;//存储当前路径,第一维表示位置 vector<vector<int>> path_best

    88730

    【手撕算法】opencv实现算法

    本文利用opencv实现了深度优先搜索DFS和广度优先搜索BFS两个算法来也是用opencv+鼠标画的。 具体代码: #define WINDOW_1 "地图" //显示绘制的地图 #define WINDOW_2 "游戏" //显示的过程 #define show_speed //绘制部分 bool g_bDrawingBox = false; //绘制标识符 int step = 25; //的步长(25*25为基本单位,一块一块的) Mat wallImage 其中 int step = 25; //的步长(25*25为基本单位,一块一块的) 代表步长,长宽均500,每一个搭建的砖是25*25大小的,在时也是按25*25的步长进行分析的 下图为绘制好的图,上边为入口,左边为出口: 深度优先搜索DFS算法 算法原理仅简单介绍: 深度优先搜索,重点是深度,以为例,当一个小人一步步往前到岔路口A时,可以向下或者向右,他会按照顺时针

    13310

    Data Structure_Visualization概率模拟排序可视化生成

    显示 生成等等再提,先看一下的读取和显示。 ? 第一行是行数和列数,代表有101行101列,这个后面可以使用最小生成树生成。 问题 白色方块是可以的路径,红色的就是墙。的本质就是一个图结构。可以把整个当成是一个图,而的过程就可以等价成是图的遍历。从起始点开始遍历,直到遍历到了某一个终止点即可。 首先固定了每一个的出口和入口位置,从一开始,就需要从相邻的四个方向,如果可以就继续,不能就回头,其实就是递归实现。 生成 刚刚是,刚刚生成的那个用例其实就是生成的。对于一个,只有一个入口一个出口,为了简单化,入口就是第二行的第一个口,出口是倒数第二行的第一个口。 首先其实就是一棵树,每一个点都会有分支,任何一个叶子或者是节点都可以作为是一个入口,生成一个其实就是一个生成树的过程。

    28160

    童年的游戏,Python一行代码就能玩

    大家好,儿童节就要来了,虽然秃头程序员没有头发,但是童心还是一直都在的,今天就分享一个私藏的GitHub项目——free-python-games,一行代码就能进入使用Python开发的小游戏快乐玩耍! 只需要更换游戏名即可启动 python -m freegames.flappy ? 这次需要不断点击鼠标来控制绿色小圆点飞行,实测比flappy bird难度要更高一点 Memory Memory翻译过来是记忆,该游戏给出一些格,点击每一个小格会显示背后藏的数字,但会快速消失,当你成功选中两个相同的数字之后就会显示为拼图 ,可玩性还是很高的 python -m freegames.memory ? 这个游戏应该就不用介绍了,找出对应的路径即可 python -m freegames.maze ?

    84731

    【重磅】Nature子刊 | 增强学习强化,混合脑生化鼠“”能力大幅提升

    在一次试验中,只要当小鼠机器人连续 3 次成功到达终点,才能被视为学会了这一个。 实验中,计算机采用的增强算法是 Q-Learning。 ? 中一共设置了 6 个决策点,这些决策点的方向可以被随机设置为向左或向右,因此一共有 64 种不同的组合。 此外,对照组平均需要 6 次才能学会,比起平均在第 3 次就学会的小鼠机器人要慢了很多。 为了验证生化鼠是否学会了将学到的规则用于探索,研究人员进行了第二次试验。 结果,相比没有计算系统增强的对照组,经过增强的 V2 鼠在时表现出了强大的学习能力,只要 2 次就能学会(对照组需要 5 次)。 这一次,V2 鼠第一次的正确率就达到了大约 80%,平均只用 2 次就能够,比此前的对照组水平都有了显著提升。 ? 实验中计算机生成的图像。

    63180

    Java版的开源 Flappy Bird 复刻项目

    最近我还整理了一批包括C++、java、Python、JavaScript等各种语言,还有操作系统、数据结构、设计、网络等各方面的学习资料,大家可以关注公众号TJ君,回复武功秘籍领取。 MazeBattles 一款用Node.js 和 Socket.io编写的小游戏,看着像是小时候玩的最最原始的2D。 扯远了,我们继续说这个MazeBattles,它采用了 Prim's MST 算法来实时生成,又使用了Breadth-First Search (BFS) 算法来求得出的解决方案。 一共有个难度,分别是easy、medium、hard、expert,逐步上升,这个从的大小就可以看的出: 除了单人模式,MazeBattles还提供了多人对战模式,是不是比小时候记忆中一个个小伙伴轮流玩更有意思呢

    9420

    python练习题参考答案来了(超多代码),看一下?(1)

    python基础语法很OK?做几题测试一下 python基础语法很OK?做几题测试一下(2) python解决能力很OK? 同理问题也是如此。 上面的说的暴力循环说起来很简单,但是也有些问题需要面对: 如何保证能够穷举出所有情况,不遗漏? 比如3,4,5,6,四个数字,可以组合成多少种不重复的3位数? (找零钱很好判断,和数独就稍微麻烦一点)。 数据量大了,搞了很久没出结果,怎么加快一些速度? ...... 给定一个大小为5*6的,由通道(0)和墙壁(1)组成,其中通道左上角表示起点,通道右下角表示终点,找到路径。 给定一个大小为5*5的,由通道(0)和墙壁(1)组成,其中通道左上角表示起点,通道右下角表示终点,找到最短路径。

    5010

    相关产品

    • 消息队列 TDMQ

      消息队列 TDMQ

      消息队列 TDMQ 是基于 Apache 顶级开源项目Pulsar自研的金融级分布式消息中间件,是一款具备跨城高一致、高可靠、高并发的分布式消息队列,拥有原生Java 、 C++、Python、GO 多种API, 支持 HTTP 协议方式接入,可为分布式应用系统提供异步解耦和削峰填谷的能力,同时也具备互联网应用所需的海量消息堆积、高吞吐、可靠重试等特性。

    相关资讯

    热门标签

    扫码关注云+社区

    领取腾讯云代金券