你的位置:首页 > 软件开发 > Java > 连连看算法实现 —— 分治实现

连连看算法实现 —— 分治实现

发布时间:2016-04-08 17:00:20
有人问我“连连看算法怎么实现?”我说“保存进二维数组中,然后判断两个点之间是否能够连通”“怎么判断是否连通?”我说“判断它们之间的连线拐角不 ...

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

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

“怎么判断是否连通?”

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

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

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

连连看的核心算法就像上文提及的:判断两个点之间的连线拐角不超过两个。那么不超过两个无外乎三种情况: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;  }

原标题:连连看算法实现 —— 分治实现

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

可能感兴趣文章

我的浏览记录