今天在收到一道的面试题，觉得比较有意思，决定记录下来，整个题目与解答过程大概如下。
连连看是一种很受大家欢迎的小游戏。下面四张图给出了最基本的消除规则：
图 A 中出现在同一直线上无障碍的圈圈可以消除；图 B 中两个圈圈可以通过一次转弯消除；图 C 和图 D 中，两个圈圈可以通过两次转弯消除。
请写一个函数来判断给定的任意两个圈圈是否可消除（x1, y1与x2, y2为两个圈圈的位置）：
public static boolean canBeRemoved(int[][] array, int x1, int y1, int x2, int y2)位置(x, y)上有无障碍物：
public static boolean isBlocked(int[][] array, int x, int y) { if (array[x][y] == 0) { return false; } return true; }水平检测用来判断两个点的纵坐标是否相等，同时判断两点间有没有障碍物。
因此直接检测两点间是否有障碍物就可以了，代码如下：
public static boolean horizon(int[][] array, int x1, int y1, int x2, int y2) { if (x1 == x2 && y1 == y2) { return false; } if (x1 != x2) { return false; } int startY = Math.min(y1, y2); int endY = Math.max(y1, y2); for (int j = startY + 1; j < endY; j++) { if (isBlocked(array, x1, j)) { return false; } } return true; }垂直检测用来判断两个点的横坐标是否相等，同时判断两点间有没有障碍物。
同样地，直接检测两点间是否有障碍物，代码如下：
public static boolean vertical(int[][] array, int x1, int y1, int x2, int y2) { if (x1 == x2 && y1 == y2) { return false; } if (y1 != y2) { return false; } int startX = Math.min(x1, x2); int endX = Math.max(x1, x2); for (int i = startX + 1; i < endX; i++) { if (isBlocked(array, i, y1)) { return false; } } return true; }
一个拐角检测可分解为水平检测和垂直检测，当两个同时满足时，便两点可通过一个拐角相连。即：
一个拐角检测 = 水平检测 && 垂直检测
A 点至 B 点能否连接可转化为满足任意一点：
A 点至 C 点的垂直检测，以及 C 点至 B 点的水平检测；A 点至 D 点的水平检测，以及 D 点至 B 点的垂直检测。代码如下：
public static boolean turnOnce(int[][] array, int x1, int y1, int x2, int y2) { if (x1 == x2 && y1 == y2) { return false; } int c_x = x2, c_y = y1; if (!isBlocked(array, c_x, c_y)) { if (vertical(array, x1, y1, c_x, c_y) && horizon(array, c_x, c_y, x2, y2)) { return true; } } int d_x = x1, d_y = y2; if (!isBlocked(array, d_x, d_y)) { if (horizon(array, x1, y1, d_x, d_y) && vertical(array, d_x, d_y, x2, y2)) { return true; } } return false; }
两个拐角检测可分解为一个拐角检测和水平检测或垂直检测。即：
两个拐角检测 = 一个拐角检测 && (水平检测 || 垂直检测)
如图，水平、垂直分别穿过 A B 共有四条直线，扫描直线上所有不包含 A B 的点，看是否存在一点 C ，满足以下任意一项：
A 点至 C 点通过水平或垂直检测，C 点至 B 点可通过一个拐角连接。（图中用 C 表示）A 点至 C 点可通过一个拐角连接，C 点至 B 点通过水平或垂直连接。（图中用 C 下划线表示）代码如下：
public static boolean turnTwice(int[][] array, int x1, int y1, int x2, int y2) { if (x1 == x2 && y1 == y2) { return false; } int max_x = array.length; int max_y = array[0].length; for (int i = 0; i < max_x; i++) { for (int j = 0; j < max_y; j++) { if ((i != x1 && i != x2 && j != y1 && j != y2)) { continue; } if ((i == x1 && j == y1) || (i == x2 && j == y2)) { continue; } if (isBlocked(array, i, j)) { continue; } if (turnOnce(array, x1, y1, i, j) && (horizon(array, i, j, x2, y2) || vertical(array, i, j, x2, y2))) { return true; } if ((horizon(array, x1, y1, i, j) || vertical(array, x1, y1, i, j)) && turnOnce(array, i, j, x2, y2)) { return true; } } } return false; }
最后，整合以上四种情况，判断两点是否能消除的代码可以写成：
public static boolean canBeRemoved(int[][] array, int x1, int y1, int x2, int y2) { if (horizon(array, x1, y1, x2, y2) || vertical(array, x1, y1, x2, y2) || turnOnce(array, x1, y1, x2, y2) || turnTwice(array, x1, y1, x2, y2)) { return true; } return false; }测试用例：
public static void main(String[] args) { int[][] array1 = { { 0, 0, 0, 0, 0, 0, 0 }, { 1, 1, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 1 }, { 0, 0, 0, 0, 0, 0, 0 } }; System.out.println(canBeRemoved(array1, 1, 1, 5, 5)); // false int[][] array2 = { { 0, 0, 0, 0, 0, 0, 0 }, { 1, 1, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 1 }, { 0, 0, 0, 0, 0, 0, 0 } }; System.out.println(canBeRemoved(array2, 1, 1, 5, 5)); // true int[][] array3 = { { 0, 0, 0, 0, 0, 0, 0 }, { 1, 1, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1, 1, 1 }, { 0, 0, 0, 0, 0, 0, 0 } }; System.out.println(canBeRemoved(array3, 1, 1, 5, 5)); // false }