在找实习面试的时候，有一位面试官问过我一个非常有意思的面试题，如何设计一个连连看游戏。
作为一个学习计算机的学生，可能先要做的是去理解问题，在这个过程中可以尽情地去问面试官问题，沟通可能比写好代码更重要。
下面是我问面试官的几个问题：
1、连连看游戏的规则是什么？
面试官给我打开了一个手机应用，解释了一下。其中最重要的是如何判断两个图形能否相消。（两个同样的图用线相连，连线拐的弯不能超过两个）
2、最多有多少张图？
一般练练看游戏是20*20或者 30*30，所以图片最多大概在1000张左右。
3、如果两个图能够消除，是直接把两个图消除？还是找到最短路径后，把路径画出来，然后再消除？
最短路径的问题可以之后考虑，先考虑简单的，直接消除两个图。
4、连连看游戏是否存在死锁状态？是否需要解除死锁状态？
在玩连连看游戏的时候，如果图片是随机摆放的，可能会碰到死锁状态。因为死锁状态很影响用户体验，所以需要解决。
搞清楚了问题之后，我们就可以分析和解决问题了。先写一个连连看游戏的程序伪代码。
initGame();// 生成游戏初始化状态while(!isGameOver()){//如果游戏没有结束if(isDeadlock()){//如果出现死锁情况unlock();//解除死锁}waitClick();//等待用户点击游戏中的图 curClick = getCurrentClick();//得到当前输入if(isLegalInput(curClick) && preClick==null){//如果当前是合法输入，并且是第一次点击preClick = curClick;curClick = null;}if(preClick!=null && curClick!=null){//如果已经点了两个图if(findPath(preClick, curClick)){//如果两个图之间存在一条连线remove(preClick, curClick);//消除这两个图preClick = null;curClick = null;//还原状态}else{preClick = curClick;curClick = null;//要被连得图变成最近一次点击的图}} }
- 生成游戏初始状态。
我们先假设有25张不同的图，连连看游戏的大小是20*20，那么我们在25张图中有放回的随机抽样200次即可，然后再把这200张图复制一遍，变成400张图。最后，我们需要把这400张图随机地放到一个20*20的二维空间中。
public class Lianliankan {private int[][] grid;//一个二维数组，里面的数字代表着图片的id，id=0时代表着空白。其中第一行和最后一行，第一列和最后一列都是空白。private int size;//size*size的连连看游戏网格private int pictureNum;//不同图的数量，编号为1到pictureNum。public Lianliankan(int size, int pictureNum){this.size = size;this.pictureNum = pictureNum;grid = new int[size+2][size+2];//网格第一行和最后一行，第一列和最后一列都是空白。 }//初始化连连看游戏public void initGame(){int[] pictures = new int[size*size];//用该数组来保存随机选出的图。Random rand = new Random();//进行有放回的抽样for(int i=0;i<size*size;){int randomPicture = rand.nextInt(pictureNum) + 1;pictures[i++] = randomPicture; pictures[i++] = randomPicture;}//打乱图片的顺序for(int i=0;i<size*size;i++){int randomPos = rand.nextInt(size*size - i) + i;exchangePosition(pictures, i, randomPos);}//向网格中摆放图片for(int i=0;i<size;i++){for(int j=0;j<size;j++){grid[i+1][j+1] = pictures[i*size+j];}}//打印网格信息for(int i=0;i<grid.length;i++){for(int j=0;j<grid[0].length;j++){System.out.print(grid[i][j] + "\t");}System.out.println();}}public static void exchangePosition(int[] pictures, int i, int j){int tmp = pictures[i];pictures[i] = pictures[j];pictures[j] = tmp;}public static void main(String[] args){Lianliankan lianliankan = new Lianliankan(20, 25);lianliankan.initGame();// 生成游戏初始化状态 } }
- 判断游戏是否结束。
游戏结束的条件就是所有的图片都被连线并且消除了，我们可以通过加入一个变量existPictureNum，来记录当前网格中存在的图片数量，当existPictureNum为0时，所有图片都已经消除，游戏也就结束了。实现就是下面加粗的代码。
public class Lianliankan {private int[][] grid;//一个二维数组，里面的数字代表着图片的id，id=0时代表着空白。其中第一行和最后一行，第一列和最后一列都是空白。private int size;//size*size的连连看游戏网格private int pictureNum;//不同图的数量，编号为1到pictureNum。private int existPictureNum;//用于记录当前网格中的图的数量public Lianliankan(int size, int pictureNum){this.size = size;this.pictureNum = pictureNum;grid = new int[size+2][size+2];//网格第一行和最后一行，第一列和最后一列都是空白。this.existPictureNum = 0;}//初始化连连看游戏public void initGame(){int[] pictures = new int[size*size];//用该数组来保存随机选出的图。Random rand = new Random();//进行有放回的抽样for(int i=0;i<size*size;){int randomPicture = rand.nextInt(pictureNum) + 1;pictures[i++] = randomPicture; pictures[i++] = randomPicture;}//打乱图片的顺序for(int i=0;i<size*size;i++){int randomPos = rand.nextInt(size*size - i) + i;exchangePosition(pictures, i, randomPos);}//向网格中摆放图for(int i=0;i<size;i++){for(int j=0;j<size;j++){grid[i+1][j+1] = pictures[i*size+j];existPictureNum++;}}//打印网格信息for(int i=0;i<grid.length;i++){for(int j=0;j<grid[0].length;j++){System.out.print(grid[i][j] + "\t");}System.out.println();}}public static void exchangePosition(int[] pictures, int i, int j){int tmp = pictures[i];pictures[i] = pictures[j];pictures[j] = tmp;}private boolean isGameOver(){return existPictureNum==0;}public static void main(String[] args){Lianliankan lianliankan = new Lianliankan(20, 25);lianliankan.initGame();// 生成游戏初始化状态while(!lianliankan.isGameOver()){//如果游戏没有结束//喝杯咖啡 }} }
- 判断连连看游戏是否是死锁状态。
最直观的想法是遍历一下网格，碰到一个图时，看看该图是否能够和另一个图进行连线。找到一个可以连线的图，就不是死锁状态；否则，是死锁状态。
- 如果是死锁状态，将其解锁。
- 得到当前输入。
- 判断是否为合法收入。
- 判断两个图之间是否存在一条连线。
- 消除两个图。