admin管理员组

文章数量:821235

一笔画完破解(上)

一笔画完是最近朋友给我推荐的一个小游戏(微信小程序),游戏规则是一笔画完全部格子,不能重复,不能有空缺,休闲类游戏,感觉挺有意思的,于是我就是想用java来帮我实现通关这个游戏,游戏界面如下。(第一篇博客讲怎么破解,第二篇实现完全自动化)不管哪一关都可以用这个代码0.1s内自动破解找到答案!

最终效果如图:

以下是教程,源码在第二篇,直接去第二篇。

附第一篇博客结果动图:

熟悉编程的朋友肯定会说用栈来保存走过的位置,不难啊,难度确实不大,本篇主要是个人兴趣,记录分享一下,且难度不在算法其实,因为时间复杂度最大的暴力破解也可以在0.1秒内破解完毕,更主要的是实现图像识别和自动化闯关。

问题分析:先把问题简化,思考下面的问题怎么解

很容易想到的是直接一笔画完了,现在我们回过头捋一下思维,我们是怎么找到这个解的,首先有一个起点,先看他能往哪里走,然后走一步试试,如果没通关的话,继续看看能往哪里走。

于是首先得出暴力破解方式:使用递归,传入当前位置,计算能往哪里走,能走则调用自身,否则尝试下一个方向,直到通关。大概思路如下如下

function step( 当前位置 ){

    if 通关?

      return

   if 能向上走?

       step( 当前位置.上面一格 )

   if 能向下走?

       step( 当前位置.下面一格 )

 //同理左右一样...

}

虽然这种算法非常笨,但是一种解决方案了,算法的优化我们在需要的时候在进行(对于计算机来说这点方格根本不是事),下面把问题转换为计算机能理解的结构:

我用int 类型二维数组数组 来表示这个问题(如果想优化算法,可以采用其他数据结构或自定义),我把不可以走的地方设置为-1,把可以走但没走的地方可以设置为0,把走过的路线按照走的顺序计数,比如起点为1,第二步为2,第三步为3...

画了个丑丑的图,勉强看一下

好了,思路有了,该怎么解呢,代码如下

public void solve(int nowX, int nowY) {tryNum++;if(hasWin())return;if(!hasWin && nowY > 0 && array[nowX][nowY - 1] == 0) {//System.out.println("←");array[nowX][nowY - 1] = ++step;solve(nowX, nowY - 1);}//leftif(!hasWin && nowY < column-1 && array[nowX][nowY + 1] == 0) {//System.out.println("→");array[nowX][nowY +1] = ++step;solve(nowX, nowY +1);}//rightif(!hasWin && nowX > 0 && array[nowX - 1][nowY] == 0) {//System.out.println("↑");array[nowX - 1][nowY] = ++step;solve(nowX - 1, nowY);}//upif(!hasWin && nowX < row -1 && array[nowX + 1][nowY] == 0) {//System.out.println("↓");array[nowX + 1][nowY] = ++step;solve(nowX + 1, nowY);}//downif(!hasWin && array[nowX][nowY] != 1) {array[nowX][nowY] = 0;step--;}//如果走到这发现上下左右都不能走,并且还没有胜利,那就是走的不对,本格子置0,退回上一步}

大概的代码,hasWin是是否胜利,判断方式是当前的步数==总的可以走的格子数?有为0的格子?未过关:过关:未过关,

虽然还有很多地方可以改进,但是可以求解了已经,遇到不会的关卡也可以自己破解了,代码放下面,可以运行,不过还有很多地方可以改进,但这个计算量不大,没有改进的必要暂时,附垃圾代码:

public class Checkpoint {//public Grid[][] grids;public int row;public int column;public int startX;public int startY;/*public int nowX;public int nowY;*/public int testCount = 0;int step = 1;int[][] array;boolean hasWin = false;public int[][] getArray(){return array;}/***  array 0代表起点,1-n代表行走顺序,-1代表不可达* @param array*/public Checkpoint(int[][] array, int startX, int startY) {this.array = array;row = array.length;column = array[0].length;this.array[startX][startY] = 1;this.startX = startX;this.startY = startY;}public boolean hasWin() {for(int i = 0; i < row; i++) {for(int j = 0; j < column; j++) {if(array[i][j] == 0) {return false;}}}hasWin = true;return true;}public void solve(int nowX, int nowY) {testCount++;//MyPoint point = stack.peek();if(hasWin())return;if(!hasWin && nowY > 0 && array[nowX][nowY - 1] == 0) {//System.out.println("←");array[nowX][nowY - 1] = ++step;solve(nowX, nowY - 1);}//leftif(!hasWin && nowY < column-1 && array[nowX][nowY + 1] == 0) {//System.out.println("→");array[nowX][nowY +1] = ++step;solve(nowX, nowY +1);}//rightif(!hasWin && nowX > 0 && array[nowX - 1][nowY] == 0) {//System.out.println("↑");array[nowX - 1][nowY] = ++step;solve(nowX - 1, nowY);}//upif(!hasWin && nowX < row -1 && array[nowX + 1][nowY] == 0) {//System.out.println("↓");array[nowX + 1][nowY] = ++step;solve(nowX + 1, nowY);}//downif(!hasWin && array[nowX][nowY] != 1) {array[nowX][nowY] = 0;step--;}}public void print() {System.out.println("try:" + testCount + "   result:" + ( hasWin ?"Ok":"No Answer") + "  step:" + step);for(int i = 0; i < row; i++) {for(int j = 0; j < column; j++) {System.out.print(array[i][j] == 0 ? "□" : array[i][j] == -1 ? "■" : array[i][j]);System.out.print("\t");}System.out.println("\n\n");}}public void print_plus() {//System.out.println("try:" + testCount + "   result:" + ( hasWin ?"Ok":"No Answer"));for(int i = 0; i < row; i++) {for(int j = 0; j < column; j++) {if(array[i][j] == -1)System.out.print("■");if(array[i][j] == step) {System.out.print("End");}else {if(array[i][j] == 1) {System.out.print("Start");}if(i < row - 1 && array[i][j] == array[i + 1][j] - 1)System.out.print("↓");if(i > 0 && array[i][j] == array[i - 1][j] - 1)System.out.print("↑");if(j < column - 1 && array[i][j] == array[i][j + 1] - 1)System.out.print("→");if(j> 0 && array[i][j] == array[i][j - 1] - 1)System.out.print("←");}System.out.print("\t");}System.out.println("\n\n");}}public void print_plus2() throws Exception {TreeMap<Integer, MyPosition> map = new TreeMap<Integer,MyPosition>();for(int i = 0; i < row; i++) {for(int j = 0; j < column; j++) {map.put(array[i][j], new MyPosition(i,j));}}Iterator iterator = map.keySet().iterator();while (iterator.hasNext()) {int key = (int) iterator.next();for(int i = 0; i < row; i++) {for(int j = 0; j < column; j++) {if(array[i][j] < key) {if(array[i][j] == -1)System.out.print("■");if(array[i][j] == step) {System.out.print("End");}else {if(array[i][j] == 1) {System.out.print("Start");}if(i < row - 1 && array[i][j] == array[i + 1][j] - 1)System.out.print("↓");if(i > 0 && array[i][j] == array[i - 1][j] - 1)System.out.print("↑");if(j < column - 1 && array[i][j] == array[i][j + 1] - 1)System.out.print("→");if(j> 0 && array[i][j] == array[i][j - 1] - 1)System.out.print("←");}}else {System.out.print(" ");}System.out.print("\t");}System.out.println("\n\n");}Thread.sleep(200);for(int i = 0;i++ < 40;) {System.out.println();}}//System.out.println("try:" + testCount + "   result:" + ( hasWin ?"Ok":"No Answer"));for(int i = 0; i < row; i++) {for(int j = 0; j < column; j++) {if(array[i][j] == -1)System.out.print("■");if(array[i][j] == step) {System.out.print("End");}else {if(array[i][j] == 1) {System.out.print("Start");}if(i < row - 1 && array[i][j] == array[i + 1][j] - 1)System.out.print("↓");if(i > 0 && array[i][j] == array[i - 1][j] - 1)System.out.print("↑");if(j < column - 1 && array[i][j] == array[i][j + 1] - 1)System.out.print("→");if(j> 0 && array[i][j] == array[i][j - 1] - 1)System.out.print("←");}System.out.print("\t");}System.out.println("\n\n");}}public void caculate() {solve(startX,startY);}}

输出部分为了按照步数输出,又想直接o(1)的时间寻找那个位置(实际上是自己懒得在写一个顺序查找了)所以使用了带排序的哈希:TreeMap,放进去之后,顺序遍历即可为顺序输出,空间置换时间嘛。

主函数:

public static void main(String[] args) throws Exception {int[][] array = {{0,	  -1,	0, 0,	0,    -1},{0,     0,	0, 0,	0,    0 },{0,	   0,	0, 0,	0,    0 },{0,	   0,	0, -1,	0,    1,},{-1,   0,	0, 0,	0,	    0},{0,    0,	0, 0,	-1,	    0},{0,    0,	0, 0,	0,	    0},{0,    0,	0, 0,	0,	    0}};array[0][1] = -1;array[0][5] = -1;array[3][3] = -1;array[4][0] = -1;array[5][4] = -1;array[0][1] = -1;array[1][1] =  1;Checkpoint question = new Checkpoint(array,1,1);question.caculate();question.print_plus2();}

垃圾代码风格,凑合着看,上面为237关的例子,我们运行发现,程序一运行就能算出一个解法了,因此暂不进行寻路算法的优化(有兴趣的同学可以找找规律,仅举一个例子:终点的度为1,只可能存在一个终点,如果走了一步之后,发现有两个或以上度为1的格子,那么这一步一定走错了,继续探索也没有意义了,提前返回上一个格子)。

虽然能够1秒内解出来,但是显然不满足我们的需求,还要自己输入行列个数,哪里不能走,起点在哪里,太麻烦了。

这一篇主要讲破解方式,下一篇下一篇点这里博客我会分享一下怎么用adb+java实现完全自动化闯关。

本文标签: 一笔画完破解(上)