文章目录三、算法实现 四、演示（.0）总结
前言
上文说到，用穷举法，码出了一个符合人脑思维方式的算法 。但也留下了两个问题：1.不符合算法的有穷性，可能无法得到通关的路径；2.空间和时间复杂度高，IDEA的资源开销非常大 。（详情请看：；源码：）这回我们基于之前的代码，进行一些改进 。
一、.0的设计思路和改进之处
上篇讲到.0的设计思路是：把一笔画完的游戏界面看做一个二维整型的矩阵，每个格子由0、1填充，1为无效、走过的格子；0为未走过的格子 。格子的移动采用递归，如下 。一旦走入到死路，即重新开始 。
向上移动：行下标-1、列下标不变向下移动：行下标+1、列下标不变向左移动：行下标不变、列下标-1向右移动：行下标不变、列下标+1
还是以第15关为例，我看观察一下程序运行的过程：
这里可以看到，当程序运行到如上情况后，重新开始了 。重新开始的同时还未记录下此条“错误”路径，那程序就像一个傻瓜一样，不长记性，可能重新开始后还会重蹈覆辙 。所以我们.0的改进有两个思路：1、走入死路时，不重新开始，仅仅按照路径一格一格地回退，回退到上一个“岔口”，选择另一条选择方向；2、记录下错误路径，并在每次随机选择方向时，把错误的路径剔除出去 。
【【一笔画完】通关路径算法的Java代码实现V2.0】二、算法设计 1、回退
首先，我们先分析一下“回退”这一步需要做的步骤：
1）记录下此方向，定一个变量，flag；值为0、1、2、3，如2

文章插图
2）回退到上一个格子
3）在上一个格子的方向选择集m中去掉此方向，把m集合中的第2位置为“0”，即不能走
4）继续随机生成，如m中一个“1”都没有，即没有可选择的方向，就继续回退
这么做就可以了吗？No，只完成了一半，这样的确能做到“回退”的效果，但是会出现下面这种情况：
程序会在两条路径上持续左右摇摆，直至消耗完虚拟机内存也不会打印出通关径路 。为什么会产生这种情况呢？因为按照上面的思路，flag只是在回退时记录一个方向，而不能在更靠前的岔口上剔除错误路径 。这该如何解决？
2、解决方案
当时码到这里，代码已经有上百行了，我想在不再增加过多代码的同时解决这个问题 。因此我思考了许久，无果，除非全部推倒重做 。无奈，还是用牺牲一百行代码为代价，使用了一种比较愚蠢的方法 。
我的思路是：创建一个长度足够长的错误路径集合，因为路径的方向是由0,1,2,3来代替的，故一条路径可由这四个数字的编码组成，如上面的15关路径状态为：下—右—下—下，用数字表示为：1311 。此状态的路径，有左(2)、右(3)两条路径选择，可设置如果这两条路径都走不通，就把这两条路径(1311-2、1311-3)视为错误路径，存入错误路径集合中，然后在下一次循环中根据1311为前缀查询错误集合，把查到的结果后一位提取出来，再去掉可选择方向集合中的此方向
三、算法实现 1、新增变量、数组
//错路路径集合,长度为10W,即可存储10W条错误的路径String[] strArr = new String[100000];
//存储路径,值范围为0~3,长度为：矩阵格子总数 - 无效格子数int[] lineArr = new int[matrix[0] * matrix[1] - blankArr.length];
//路径的序号,记录此格子是路径的第几位,从0开始int lineNo = 0;

• 上一页
• 1
• 2
• 下一页

• php怎么优化搜索,导航型搜索关键词如何优化
• NB-IOT的四大特性
• 【学习摘记】马士兵JAVASCRIPT_课时2-7_JS小例子大全
• 【CSDN博客之星】专访陈勇： 敏捷开发现状及发展之路
• 从磁贴打开 浏览器主页被篡改用尽一切办法都无法完全改回来——一种可能（华为电脑
• 21、DateTime.ParseExact使用小记一
• 二 Android集成百度地图SDK笔记
• 宝尚线上炒股-下周一借东风拉放量阳线！
• 【树莓派】连接隐藏SSID WIFI
• 【项目实战】03-项目开发介绍