Openharmony 军棋工兵寻径算法的实现
一、引言
工兵可在铁路线上任意行走,其它棋子在铁路线上只能直走或 经过弧形线,不能转直角弯; 工兵在普通路线上跟其他棋子一样,走一格。但是在轨道上,就 如入无人之地了。可以在轨道上自由移动,怎样走都行,只要不超过 轨道的区域,想走多远就走多远,但是如果有个棋子(不论敌我)堵住路 线,你就不能按照那个路线行进;同时我们还要寻找到最近的路径。
二、算法分析
大体要求
1、工兵从起点到终点过程中不能有障碍物阻挡。
2、如何寻求到路径最短?且是否用时最快。
3、也有可能起点到终点是死路。
军旗的工兵走法特别像迷宫走法。
迷宫算法
1、深度优先搜索(DFS)
它和递归的探测思路是基本一致的,可以看成是递归方式的非递归版本。
2、广度优先搜索(BFS)
广度优先搜索法利用队列的特点,一层层向外扩展查找可走的方块,直到找到出口为止,最先找到的这个答案就必然是最短的。
3、根据特点我们希望最先找到最短的距离故采用bfs的方式。
采用队列来记录探测点;当前探测点的四个方向,可以通过的点,保存到这个队列中,并移除当前探测点。
右 下 左 上 的 四个方向探测。
采用一个二维数组来存储 x,y上的障碍物,和探测的点。
代码实现
(1)获取到起点和终点坐标。
(2)获取二维数组迷宫标记。
二维数组是记录棋盘上 0 是表示可通状态,1表示不可通。默认是棋盘铁路都为0可通。
然后,敌方和友方其中全部设置为不可通1。
(3)进行广度优先搜索。
(4)本案例还记录路径,采用的是链表数据结构。
每次 把prev给记录下来。这下就可以追溯到整个完整的探测路线。
(5)队列是自己利用数组改成的。
openharmony 目前 Deque、Queue 有bug,没法用;只能用数组,然后 数组的pop是最后一个,就把探测顺序插入第一个。
三,总结
可能代码直接拷贝过去跑不通。
本文也就阐述一种思维,同时体现一下openharmony目的能力可达之处。
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023