【一笔画完】通关路径算法的Java代码实现V2.0
文章目录
- 前言
- 一、OneStrokeV1.0的设计思路和改进之处
- 二、算法设计
- 1、回退
- 2、解决方案
- 三、算法实现
- 1、新增变量、数组
- 2、新增方法
- 四、演示（OneStrokeV2.0）
- 总结
前言
上文说到，用穷举法，码出了一个符合人脑思维方式的算法。但也留下了两个问题：1.不符合算法的有穷性，可能无法得到通关的路径；2.空间和时间复杂度高，IDEA的资源开销非常大。（详情请看：https://blog.csdn.net/qq_42108331/article/details/114488448；源码：https://download.csdn.net/download/qq_42108331/15782421）这回我们基于之前的代码，进行一些改进。
一、OneStrokeV1.0的设计思路和改进之处
上篇讲到OneStrokeV1.0的设计思路是：把一笔画完的游戏界面看做一个二维整型的矩阵，每个格子由0、1填充，1为无效、走过的格子；0为未走过的格子。格子的移动采用递归，如下。一旦走入到死路，即重新开始。
向上移动：行下标-1、列下标不变向下移动：行下标+1、列下标不变向左移动：行下标不变、列下标-1向右移动：行下标不变、列下标+1
还是以第15关为例，我看观察一下程序运行的过程：
这里可以看到，当程序运行到如上情况后，重新开始了。重新开始的同时还未记录下此条“错误”路径，那程序就像一个傻瓜一样，不长记性，可能重新开始后还会重蹈覆辙。所以我们OneStrokeV2.0的改进有两个思路：1、走入死路时，不重新开始，仅仅按照路径一格一格地回退，回退到上一个“岔口”，选择另一条选择方向；2、记录下错误路径，并在每次随机选择方向时，把错误的路径剔除出去。
二、算法设计
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;
2、新增方法
//将错误路径数组装换为字符串
public static String errorRoad(int arr[]){String str = "";for(int i =0; i < arr.length; i++){if (arr[i] == -1)break;str += arr[i];}return str;
}
//错误路径加入"错误路径集合"中
public static void addStr(String str, String arr[]){for(int i = 0; i < arr.length; i++){if (arr[i] == null || arr[i].startsWith(str)) {arr[i] = str;break;}}
}
//查找到错误路径的后一位数
public static void findError(String strArr[], String key, int[] m){for(int i = 0; i < strArr.length; i++){if (strArr[i] != null && strArr[i].startsWith(key) && strArr[i] != key)m[Integer.parseInt(strArr[i].substring(key.length(), key.length()+1))] = 0;else if (strArr[i] != null && strArr[i] == key)m[Integer.parseInt(strArr[i].substring(strArr[i].length() - 1, strArr[i].length()))] = 0;}
}
（注：可以思考一下startsWith()方法的妙用）
四、演示（OneStrokeV2.0）
还是以15关为例，运行结果如下：
从这两张图可以看出，程序运行到“死胡同”后没有重新开始，而是一格一格回退，回退到上一个岔口后，再走另外一条路径，如果有两条的话，就会随机选择一条。如此，程序就解决了OneStrokeV1.0中“不符合算法有穷性”的问题。因为矩阵中错误路径的数量是有限的，上篇文章说过，15关的错误路径有22条，那么程序一直跑，在“错误路径集合中的错误路径个数”大于22之前，一定是可以打印出通关路径的。（注：为什么上面图中错误路径个数达到25才打印出路径，是错误路径覆盖不完全导致的。比如13112、13113是错误路径已存入到错误路径集合中，之后发现1311也是错误路径，因为1311是13112、13113的前序步骤，故方法会把以1311为前缀的错误路径覆盖掉，但只会替换掉其中的一条——哪一条在集合前面就会被替换掉。这样就多出了一条“多余的”错误路径）
总结
简单总结一下：OneStrokeV2.0解决了OneStrokeV1.0的“不符合算法有穷性的特点”，就是说时间和内存管够，OneStrokeV2.0是可以打印出通关路径，而且OneStrokeV2.0用的是“回退”“剔除错误路径”的机制，也使打印出通关路径的速度提高了一些。
最后说一句，采用暴力破解肯定不是解决这种问题的方法，后续可以采用其他更有效的方法。
（OneStrokeV2.0代码：https://download.csdn.net/download/qq_42108331/87759059）
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！