【一笔画完】通关路径算法的Java代码实现V2.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;}}

（注：可以思考一下()方法的妙用）
四、演示（.0）
还是以15关为例，运行结果如下：
从这两张图可以看出，程序运行到“死胡同”后没有重新开始，而是一格一格回退，回退到上一个岔口后，再走另外一条路径，如果有两条的话，就会随机选择一条。如此，程序就解决了.0中“不符合算法有穷性”的问题。因为矩阵中错误路径的数量是有限的，上篇文章说过，15关的错误路径有22条，那么程序一直跑，在“错误路径集合中的错误路径个数”大于22之前，一定是可以打印出通关路径的。（注：为什么上面图中错误路径个数达到25才打印出路径，是错误路径覆盖不完全导致的。比如13112、13113是错误路径已存入到错误路径集合中，之后发现1311也是错误路径，因为1311是13112、13113的前序步骤，故方法会把以1311为前缀的错误路径覆盖掉，但只会替换掉其中的一条——哪一条在集合前面就会被替换掉。这样就多出了一条“多余的”错误路径）
总结
简单总结一下：.0解决了.0的“不符合算法有穷性的特点”，就是说时间和内存管够，.0是可以打印出通关路径，而且.0用的是“回退”“剔除错误路径”的机制，也使打印出通关路径的速度提高了一些。
最后说一句，采用暴力破解肯定不是解决这种问题的方法，后续可以采用其他更有效的方法。
（.0代码：）