你的位置:首页 > Java教程

[Java教程]连连看算法实现 —— 分治实现

有人问我“连连看算法怎么实现?”

我说“保存进二维数组中,然后判断两个点之间是否能够连通”

“怎么判断是否连通?”

我说“判断它们之间的连线拐角不超过两个”

“怎么判断拐角不超过两个?”

额,具体的实现我也不知道,于是上网找了一把,感觉大多数算法都很容易理解,实现却不简单,于是想了下怎么能把连连看的算法简单的实现,嘿!还真想出来了,至于文章标题上面还有个分治实现,则因为自己的思路感觉和分治(我对分治理解:大化小,小化更小,直到小的很容易)是一致的,所以不用去纠结分治是什么,下面开始进入正题:

连连看的核心算法就像上文提及的:判断两个点之间的连线拐角不超过两个。那么不超过两个无外乎三种情况:1、没有拐角。2、一个拐角。3、两个拐角。没有拐角最简单,我们先从它下手。

没有拐角:

既然没有拐角则只有两种可能:在同一个水平线上 或者 在同一个垂直线上,并且中间都是空白。那我们首先判断两点 X坐标 或者 Y坐标 是否相等来得出是否在一条线上,接着把两个点之间都看一遍,看看是否全部都是空的,全部都是空的,那么两点就满足相连,否则只要有一个非空,则不满足。

  //没有拐角的判定  private boolean zore(int x1,int y1,int x2,int y2){    if(x1 != x2 && y1 != y2){//两点如果不在同一水平线或者垂直线,则不可能为没有拐角相通      return false;    }    if(x1 == x2){//判断两点水平之间是否全空白      int minY = Math.min(y1, y2);      int maxY = Math.max(y1, y2);      for(int i=minY+1; i<maxY; i++){        if(checkArr[x1][i] !=0){          return false;        }      }    }else if(y1 == y2){//判断两点垂直之间是否全空白      int minX = Math.min(x1, x2);      int maxX = Math.max(x1, x2);      for(int i=minX+1; i<maxX; i++){        if(checkArr[i][y1] !=0){          return false;        }      }    }    //能执行到这里说明两点之间全是空白,所以返回true    return true;  }

没有拐角的代码实现

一个拐角:

 

画一个直角,而且还必须以固定的两个点为起点和终点,也只有两种情况,如下图所示:

图中我们A B是我们游戏中选中的两个点,那我们这两个点能满足一个拐角相连只有A->D->B A->C->B这两种情况,先看A->D->B这种情况:

我们已经知道A(x1,y1) 、B(x2,y2)两点的坐标,这时D点的坐标自然也就出来了:(x2, y1),知道了D点坐标,那么我们A-D-B这种一个拐角相连的情况就可以看做是:A到D是否没有拐角相连,并且D到B是否没有拐角相连。一个拐角相连的判断瞬间就变成两段没有拐角相连的判断,好简单有木有!!不过我们还需要注意一个小地方,如果D点不是空白,那么我们一切努力就白费了,所以加上一个判断:D点非空白,直接Pass。

private boolean one(int x1,int y1,int x2,int y2){    if(x1 == x2 || y1 == y2 ){//一个拐角需要两个坐标均不相等      return false;    }    return ( data[x1][y2]==0 &&zore(x1,y1,x1,y2)&&zore(x1,y2,x2,y2) )    ||(data[x2][y1]==0 && zore(x1,y1,x2,y1)&&zore(x2,y1,x2,y2) );      }

一个拐角的代码实现

两个拐角:

之前我们一个拐角的做法是:把问题变成没有拐角来简单化,那我们现在来考虑怎么把两个拐角的变成一个拐角的来简单化:

对于从A到B两个拐角的情况,我们可以说至少第一个拐角的位置我们知道的,“啥?第一个拐角我们知道?两个点之间两个拐角的情况那么多,别逗了!”别急,我这里说第一个拐角的位置知道是因为第一个拐角只有四种情况:A的水平左边、A的水平右边、A的垂直上边、A的垂直下边,那么要找第一个拐角点,我们只需要从A分别循环的向左、向右、向上、向下去找就是了。“那这四个方向那么多点我们怎么知道哪一个是第一个拐角点?”这个问题我也不知道,但是我知道如果点C是第一个拐角点,那么C和B之间必定可以一个拐角相连,到这里是不是两个拐角的问题又变成了一个拐角的问题,好简单有木有!有木有!有木有!重要的事情说三遍!

至于实现自然首先就是从A循环向四个方向去找空白的点,找到了就判断这个空白的点和B点是否一个拐角相连,如果找到一个非空白点或者到了边界,那么循环就可以END了!

  public boolean two(int x1,int y1,int x2,int y2){    //向左    for(int i=x1-1; i>-1; i--){      if(checkArr[i][y1]!=0){        break;      }      if( one(i,y1,x2,y2)){        return true;      }    }    //向右    for(int i=x1+1; i<checkArr.length; i++){      if(checkArr[i][y1]!=0){        break;      }      if(one(i,y1,x2,y2)){        return true;      }    }    //向上    for(int i=y1-1; i>-1; i--){      if(checkArr[x1][i]!=0){        break;      }      if(one(x1,i,x2,y2)){        return true;      }    }    //向下    for(int i=y1+1; i<checkArr.length; i++){      if(checkArr[x1][i]!=0){        break;      }      if(one(x1,i,x2,y2)){        return true;      }    }    return false;  }

两个拐角的代码实现

写在最后:不得不说这个算法不高效,但我认为它很好理解,至于最后把附上自己的完整的代码。

源码