[Word]Java下连连看算法

[Word]Java下连连看算法 建一个 C 点和一个 D 点，并且规定 C 点的横 坐标为 A 点的横坐标， C 点的纵坐标为 B 点 的纵坐标， D 点的横坐标为 B 点的横坐标， D 点的纵坐标为 A 点的纵坐标(这一点很重要，因 为 C 、 D 决定了 AC 、 BC 、 AD 、 BD 的 连线方式)，如下图: 两点之间只需要一条直线连接: boolean verticalMatch(Point a, Point b) // 竖线上的判断 boolean horizonMatch(Point a, Point b) // 横线上的判断 如果此时 C 点(或 D 点)能同时满足 AC ( java.awt 注意:为了简单省事，我们用包中的( AD )、 BC ( BD )只需要一条直线相连，Poin(x, y)t 来描述二维数组中元素的坐标，但是有就表示 A 、 B 之前能够使用两条直线连接起来， x 和 y 与二维数组中元素的下一点要特别小心，并且 C 点( D 点)为拐点(以后会用上的) 恰好相反 ，如左上图中 A 的下标为 标值 array[1][0] ， Point 的描述却是为 Point(0, 1) ， ) 如果不注意这一点，程序会出错的。//A 、 B 之间有一个拐点 boolean oneCorner(Point a, Point b) { 两点之间需要两条直线连接: Point c, d; boolean isMatch; c = new Point(a.x, b.y); d = new Point(b.x, a.y); if (map[c.x][c.y] == 0) { //C 点上必须没有 障碍 isMatch = horizonMatch(a, c) && verticalMatch (b, c); 如上图， A 、 B 两点如果需要两条直线连接起if (isMatch) { 来，有可能有两种方式，于是，我们可以巧妙的构 return isMatch; } } if (map[d.x][d.y] == 0) { //D 点上必须没有 障碍 isMatch = verticalMatch (a, d) && ( 图 B :这种方式比较容易忽略掉 ) horizonMatch (b, d); return isMatch; } return false; } ( 注意:由于 C 点和 D 点的构建方式确定了 AC 、 BD 永远是竖连线、 BC 、 AD 永远是横以上图说明了两点间三条直线的所有可能性，和二 ) 连线条直线的情况相比，拐点是两个，麻烦了一点，但 也不难处理。 两点之间需要三条直线连接: 下面我们来分析一下该怎么处理二个拐点的情况 (三条直线)。由上面的图可以看出， A 、 B 如这种方式是最复杂的了，我们还是先分析一下出现 果要通过三条直线相连，则必须有 C 、 D 两个三条直线的所有可能性吧。 拐点，如果能确定下 C 、 D ，问就好解决多 了。 怎么样来确定 C 、 D 两点呢,我们以图 A 中 的左图为例，在此之前，我们规定 C 点与 A 点 在同一竖线上， D 点与 A 点在同一直线上。同 时，从图中我们也可以看出， A 、 B 两点间如 果只能通过三条直线连接起来，则必定有一条直线 ( 图 A) 处于 A 、 B 的横向夹线纵向夹线中(如画圈的 线)。 我们假设相等的线为在 A 、 B 两点的横坐标相public Line(int direct, Point a, Point b) { 等、纵坐标为 0~Setting.ROW 构成的区域上 ( 如this.direct = direct; 图 ) 。 this.a = a; 我们先扫描出所有的线，并且我们发现，如果在 this.b = b; A 、 B 构成的区域中存在两个点能构成直线，那 } 么，这条直线就 有可能 是我们需要的直线，我们 } 称此线为符合线，如果符合线的两端( C 、 D 两 点)与 A 、 B 两点分别能 AC 、 CD 、 DB 能 同时，由于在扫描的过程中，会找到多根符合线， 构成直线的原则，则 AB 间一定可以通过三条直 因此，我们可以用 Vector 来保存这些找到的符合线连接起来。(这个可能我描述得不太清楚，但相 线(为了提高效率，也可以使用 LinkedList 来保信你应该不难明白的) 存)。 Vector vector = new Vector(); // 保存求解后我们把所有找到的符合线保存起来，并且要记录下的线 符合线是横向上的还是纵向上的，然后通过这些找 到的符合线，依次和 A 、 B 两点进行判断，一扫描两点构成的矩形内有没有完整的空白线段 旦找到这样的 C 、 D 两点，能满足 AC 、 CD 、 DB 这三条线上都没有障碍，那么， A 、 B 就 Vector scan(Point a, Point b) { 可以消除了。还是用算法来描述一下吧。 Vector v = new Vector(); // 从 a, c 连线向 b 扫描，扫描竖线 首先我们构建一个保存 C 、 D 点的类 Line ， // 扫描 A 点左边的所有线 并且要指明 C 、 D 的方向是横向还是纵向。 for (int y = a.y; y >= 0; y--) { if (map[a.x][y] == 0 && map[b.x][y] == 0 //Line.java && public class Line { verticalMatch(new Point(a.x, y), new Point(b.x, y))) { // 存在完整路线 public Point a, b; v.add(new Line(0, new Point(a.x, y), new public int direct; //1 表示横线， 0 表示竖线 Point(b.x, y))); public Line() { } } } // 扫描 A 点右边的所有线 } for (int y = a.y; y < COLUMN; y++) { return v; if (map[a.x][y] == 0 && map[b.x][y] == 0 } && 现在，我们对所有找到的符合线进行判断，看看 verticalMatch(new Point(a.x, y), new Point(b.x, y))) { // 存在完整路线 AC 、 DB 是否同样也可以消除 v.add(new Line(0, new Point(a.x, y), new Point(b.x, y))); boolean twoCorner(Point a, Point b) { } vector = scan(a, b); } if (vector.isEmpty()) { // 没有完整的空白线// 从 a, d 连线向 b 扫描，扫描横线 段，无解 // 扫描 A 点上面的所有线 return false; for (int x = a.x; x >= 0; x--) { } if (map[x][a.y] == 0 && map[x][b.y] == 0 for (int index = 0; index < vector.size(); && index++) { horizonMatch(new Point(x, a.y), new Line line = (Line) vector.elementAt(index); Point(x, b.y))) { if (line.direct == 1) { // 横线上的扫描段，找v.add(new Line(1, new Point(x, a.y), new 到了竖线 Point(x, b.y))); if (verticalMatch(a, line.a) && } verticalMatch(b, line.b)) { // 找到了解，返回 } return true; // 扫描 A 点下面的所有线 } for (int x = a.x; x < ROW; x++) { } if (map[x][a.y] == 0 && map[x][b.y] == 0 else { // 竖线上的扫描段，找到了横线 && if (horizonMatch(a, line.a) && horizonMatch(new Point(x, a.y), new horizonMatch(b, line.b)) { Point(x, b.y))) { return true; v.add(new Line(1, new Point(x, a.y), new Point(x, b.y))); } } } } if (Match(A, b)) { return false; 返回找到的 AB 点 ; } } } 寻找下一个 A 点 ; 消除该两个元素时，只需要将两个元素的值置为 0 } 即可。 找不到点 ; 更多的功能:自动寻找匹配的点 更多的功能:刷新地图 现在，算法基本上是实现了，但是，为了使游戏更 刷新地图的功能其实非常简单，只是需要将二维数丰富，我们还需要实现更多的功能，现在，我们添 组中现有的元素打乱后然后放回这个二维数组):加一个自动寻找匹配的点的功能。 找到地图中所有的值不为 0 的点并且保存到一该功能需要分两步走: 维数组中 打乱一维数组 第一步，从左上向右下搜索二维数组中第一个值不 重新分配回二维数组中 为 0 的元素 A ，找到该点后，然后再从该点向 后找到一个值与该点值相等的元素 B ，然后对这 两个元素进行是否可消除的判断，如果可以消除， 则说明该两点匹配，如果不能消除，则继续寻找与 A 点值相等的 B 点，如果找不到 B 点，则寻找 下一个 A 点，依次下去，直到找不到这个 A 点， 这就表时地图上已经不存在可消除的点了，我们用 伪算法描述如下: 找到第一个 A 点 while (A 点存在时 ) { while ( 能找到与 A 点值相等的 B 点 ) {