08 连连看

本文主要是介绍08 连连看，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 前言

这是在贴吧看见一位大神做的练练看外挂, 感觉那个场景挺炫酷的, 后来没事就自己做了连连看

备注 : 图片来自这里写图片描述
是不是亮瞎了。。[利用程序截几张图便是素材]

难点主要 : 在于寻路的算法, 以及绘制路径, 还有一个就是, 对于一个结合中如何迭代出每次抽取两个元素的所有组合
规则 : 最多可以使用两次转弯, 来寻找两个相同的图片

元素介绍 :
图片 : 每一个矩形格中对应的显示的图片
这里写图片描述

2. 基本的数据结构介绍

2.1 PictureMatching : 连连看核心Model, 其接口如下 :
parse() : 解析整个练练看, 遍历sameNodes, 遍历sameNodes中的任意两个结点 , 如果其可以相互到达则设置pics的该位置为NULL, 并从sameNodes中删除该两个结点, 之后判断是否游戏完成如果是的话表示游戏完成了跳出循环, 如果存在死锁则跳出循环, 否则继续遍历sameNodes …
canReach(Node src, Node dst) : 先获取dst相对于src的位置在根据位置的不同做出不同的处理
getMovePath() : 获取移动的路径[如果两个照片能相互到达]
removeNodes(Node first, Node second, int i) : 移除两个可以相互到达的相同图片, 并通知observer, 绘制图片

/*** file name : PictureMatching.java* created at : 11:08:12 AM May 13, 2015* created by 970655147*/package com.hx.pictureMatching;// 连连看核心Model
public class PictureMatching {// NULL表示该位置的数据已经被消除// pics存放"照片序列"的逻辑表示// sameNodes存放各个相同的图片// sameNodesSize表示上一次解析之后  还剩余多少照片// isDeadLock 表示是否存在死锁// movePath 表示上一次的能够到达的两个图片的路径// dpObs, 表示绘制路径的listener// dlObs, 表示监听死锁的listener   public static int NULL = -1;private Integer[][] pics;private SameNodes[] sameNodes;private int sameNodesSize;private boolean isDeadLock;private LinkedList<Node> movePath;private MainPanel panel;private Observer dpObs;private Observer dlObs;// 初始化public PictureMatching() {}public PictureMatching(Integer[][] pics) {this.pics = pics;sameNodes = new SameNodes[Tools.PIC_NUM];sameNodesSize = pics.length * pics[0].length;movePath = new LinkedList<Node>();dpObs = new PMDrawPathObserver();dlObs = new DeadLockObserver();init();}// 初始化sameNodesprivate void init() {isDeadLock = false;// 解析创建sameNodes  并向其添加Nodefor(int i=0; i<sameNodes.length; i++) {sameNodes[i] = new SameNodes(i);}for(int i=0; i<Tools.HEIGHT; i++) {for(int j=0; j<Tools.WIDTH; j++) {if(pics[i][j] != NULL) {sameNodes[pics[i][j]].add(new Node(i, j));}}}}// 解析整个练练看// 遍历sameNodes, 遍历sameNodes中的任意两个结点  // 如果其可以相互到达  则设置pics的该位置为NULL, 并从sameNodes中删除该两个结点// 之后 判断是否游戏完成   如果是的话 表示游戏完成了跳出循环// 如果存在死锁  则跳出循环// 否则  继续遍历sameNodes ...public void parse() {// 打印日志Log.log("original matrix as follow : ");logPics();boolean isEnd = false;System.out.println("removed elements : ");do {for(int i=0; i<sameNodes.length; i++) {if(sameNodes[i].haveNodes()) {      PairIter iter = sameNodes[i].pairIter();while(iter.hasNext()) {Node[] nodes = iter.next();if(canReach(nodes[0], nodes[1])) {// ...removeNodes(nodes[0], nodes[1], i);iter.updateAfterFindMatched();}                   }}}isEnd = !hasNonMatchedPicture(sameNodes);if(isDeadLock) {handleDeadLock();break;}} while(!isEnd);// 打印日志Log.enter(2);Log.log("result matrix as follow : ");logPics();}// 处理死锁的相关业务private void handleDeadLock() {Log.enter(1);Log.horizon(2);System.out.println("deadLock exists, game over....");dlObs.update(panel, null);}// 移除两个可以相互到达的相同图片, 并通知observer, 绘制图片public void removeNodes(Node first, Node second, int i) {Log.log(first.toString() + " -> " + second.toString());clear(first);clear(second);sameNodes[i].remove(first);sameNodes[i].remove(second);if(panel != null) {DrawPathEvent dpe = new DrawPathEvent();dpe.setNodes(new Node[]{first, second});dpObs.update(panel, dpe);}}public void setPics(Integer[][] pics){this.pics = pics;init();}public int getNodeValue(Node node) {return pics[node.row][node.col];}private void setNodeValue(Node node, int newVal) {pics[node.row][node.col] = newVal;}// 返回是否 还有图片  如果是的话继续解析// 如果这次计算的剩下的图片数量 和上次计算的图片数量一致  则说明当前"图片序列"存在死锁   更新相关标志位private boolean hasNonMatchedPicture(SameNodes[] sameNodes2) {int sum = 0;for(int i=0; i<sameNodes2.length; i++) {sum += sameNodes2[i].size();}if(sum == sameNodesSize) {isDeadLock = true;} else {sameNodesSize = sum;}return sum > 0;}// 清理node位置的数据private void clear(Node node) {setNodeValue(node, NULL);}// 判断src是否可到达dst// 先获取dst相对于src的位置  在根据位置的不同  做出不同的处理public boolean canReach(Node src, Node dst) {int direction = getDirection(src, dst);boolean canReach = false;
//      Log.log(direction);switch(direction) {case Tools.UP_LEFT:canReach = canReachForUpLeft(src, dst);break;case Tools.UP:canReach = canReachForUp(src, dst);break;case Tools.UP_RIGHT:canReach = canReachForUpRight(src, dst);break;case Tools.RIGHT:canReach = canReachForRight(src, dst);break;case Tools.DOWN_RIGHT:canReach = canReachForUpLeft(dst, src);break;case Tools.DOWN:canReach = canReachForUp(dst, src);break;case Tools.DOWN_LEFT:canReach = canReachForUpRight(dst, src);break;case Tools.LEFT:canReach = canReachForRight(dst, src);break;default :throw new RuntimeException("have no this direction...");}return canReach;}// 表示dst在src的左上方// 尝试一下方案, 判断其是否可以到达// 1. 向左移动 在向上移动// 2. 向上移动 在向左移动// 3. 向上移动 在向左移动 在向上移动// 4. 向左移动 在向上移动 在向左移动// 5. 向右移动 在向上移动 在向左移动// 6. 向左移动 在向上移动 在向右移动// 7. 向上移动 在向左移动 在向下移动// 8. 向下移动 在向左移动 在向上移动private boolean canReachForUpLeft(Node src, Node dst) {// 1. 向左移动 在向上移动int directions[] = new int[]{Tools.LEFT, Tools.UP};boolean canLeftUp = reachInOneUpdate(src, dst, directions);if(canLeftUp) {return true;}// 2. 向上移动 在向左移动directions = new int[]{Tools.UP, Tools.LEFT};boolean canUpLeft = reachInOneUpdate(src, dst, directions);if(canUpLeft) {return true;}// 3. 向上移动 在向左移动 在向上移动directions = new int[]{Tools.UP, Tools.LEFT, Tools.UP};boolean canUpLeftUp = reachInTwoUpdate(src, dst, directions);if(canUpLeftUp) {
//          Log.horizon();return true;}// 4. 向左移动 在向上移动 在向左移动directions = new int[]{Tools.LEFT, Tools.UP, Tools.LEFT};boolean canLeftUpLeft = reachInTwoUpdate(src, dst, directions);if(canLeftUpLeft) {return true;}// 5. 向右移动 在向上移动 在向左移动directions = new int[]{Tools.RIGHT, Tools.UP, Tools.LEFT};boolean canRightUpLeft = reachInTwoUpdate(src, dst, directions);if(canRightUpLeft) {return true;}// 6. 向左移动 在向上移动 在向右移动directions = new int[]{Tools.LEFT, Tools.UP, Tools.RIGHT};boolean canLeftUpRight = reachInTwoUpdate(src, dst, directions);if(canLeftUpRight) {return true;}// 7. 向上移动 在向左移动 在向下移动directions = new int[]{Tools.UP, Tools.LEFT, Tools.DOWN};boolean canUpLeftDown = reachInTwoUpdate(src, dst, directions);if(canUpLeftDown) {return true;}// 8. 向下移动 在向左移动 在向上移动directions = new int[]{Tools.DOWN, Tools.LEFT, Tools.UP};boolean canDownLeftUp = reachInTwoUpdate(src, dst, directions);if(canDownLeftUp) {return true;}return false;}// 表示dst在src的正上方// 尝试一下方案, 判断其是否可以到达// 1. 直接向上移动// 2. 向右移动 在向上移动 在向左移动// 3. 向左移动 在向上移动 在向右移动private boolean canReachForUp(Node src, Node dst) {// 1. 直接向上移动boolean canReachUpDirectly = canReachDirectly(src, dst, Tools.UP);if(canReachUpDirectly) {return true;}// 2. 向右移动 在向上移动 在向左移动int directions[] = new int[]{Tools.RIGHT, Tools.UP, Tools.LEFT};boolean canRightUpLeft = reachInTwoUpdate(src, dst, directions);if(canRightUpLeft) {return true;}// 3. 向左移动 在向上移动 在向右移动directions = new int[]{Tools.LEFT, Tools.UP, Tools.RIGHT};boolean canLeftUpRight = reachInTwoUpdate(src, dst, directions);if(canLeftUpRight) {return true;}return false;}// 表示dst在src的左上方// 尝试一下方案, 判断其是否可以到达// 这里的注释不准确, 详见参数！！！// 1. 向左移动 在向上移动// 2. 向上移动 在向左移动// 3. 向上移动 在向左移动 在向上移动// 4. 向左移动 在向上移动 在向左移动// 5. 向右移动 在向上移动 在向左移动// 6. 向左移动 在向上移动 在向右移动// 7. 向上移动 在向左移动 在向下移动// 8. 向下移动 在向左移动 在向上移动private boolean canReachForUpRight(Node src, Node dst) {// 1. 向左移动 在向上移动int directions[] = new int[]{Tools.RIGHT, Tools.UP};boolean canLeftUp = reachInOneUpdate(src, dst, directions);if(canLeftUp) {return true;}// 2. 向上移动 在向左移动directions = new int[]{Tools.UP, Tools.RIGHT};boolean canUpLeft = reachInOneUpdate(src, dst, directions);if(canUpLeft) {return true;}// 3. 向上移动 在向左移动 在向上移动directions = new int[]{Tools.UP, Tools.RIGHT, Tools.UP};boolean canUpLeftUp = reachInTwoUpdate(src, dst, directions);if(canUpLeftUp) {return true;}// 4. 向左移动 在向上移动 在向左移动directions = new int[]{Tools.RIGHT, Tools.UP, Tools.RIGHT};boolean canLeftUpLeft = reachInTwoUpdate(src, dst, directions);if(canLeftUpLeft) {return true;}// 这两个和上面的canReachForUpLeft一致// 5. 向右移动 在向上移动 在向左移动directions = new int[]{Tools.RIGHT, Tools.UP, Tools.LEFT};boolean canRightUpLeft = reachInTwoUpdate(src, dst, directions);if(canRightUpLeft) {return true;}// 6. 向左移动 在向上移动 在向右移动directions = new int[]{Tools.LEFT, Tools.UP, Tools.RIGHT};boolean canLeftUpRight = reachInTwoUpdate(src, dst, directions);if(canLeftUpRight) {return true;}// 7. 向上移动 在向左移动 在向下移动directions = new int[]{Tools.UP, Tools.RIGHT, Tools.DOWN};boolean canUpLeftDown = reachInTwoUpdate(src, dst, directions);if(canUpLeftDown) {return true;}// 8. 向下移动 在向左移动 在向上移动directions = new int[]{Tools.DOWN, Tools.RIGHT, Tools.UP};boolean canDownLeftUp = reachInTwoUpdate(src, dst, directions);if(canDownLeftUp) {return true;}return false;}// 表示dst在src的正上方// 尝试一下方案, 判断其是否可以到达// 这里的注释不准确, 详见参数！！！// 1. 直接向上移动// 2. 向右移动 在向上移动 在向左移动// 3. 向左移动 在向上移动 在向右移动private boolean canReachForRight(Node src, Node dst) {// 1. 直接向上移动boolean canReachUpDirectly = canReachDirectly(src, dst, Tools.RIGHT);if(canReachUpDirectly) {return true;}// 2. 向右移动 在向上移动 在向左移动int directions[] = new int[]{Tools.UP, Tools.RIGHT, Tools.DOWN};boolean canRightUpLeft = reachInTwoUpdate(src, dst, directions);if(canRightUpLeft) {return true;}// 2. 向左移动 在向上移动 在向右移动directions = new int[]{Tools.DOWN, Tools.RIGHT, Tools.UP};boolean canLeftUpRight = reachInTwoUpdate(src, dst, directions);if(canLeftUpRight) {return true;}return false;}// 判断src能否沿着direction方向到达dst// 获取src的direction方向的下一个结点// 如果该node不为dst并且 该可以移动到该节点  一直沿着direction方向移动// 如果 node在边界上[边界上认为是可移动的]  直接跳出循环// 跳出循环之后  如果 node为dst  则返回true// 否则  返回falseprivate boolean canReachDirectly(Node src, Node dst, int direction) {movePath.clear();movePath.add(src);Node node = nextNode(src, direction);while(!node.eq(dst) && isNodeMovable(node)) {movePath.add(new Node(node));node.move(direction);if(node.isInOutBounds()) {break;}}if(node.eq(dst) ) {movePath.add(new Node(node));return true;}return false;}// 判断src能否沿着directions方向到达dst  经过两次转弯// 获src第一个方向上的下一个结点// 接下来的两个boolean标志 主要是用于  使下一次循环的时候  直接进入第二个方向   具体的条件 请参见代码// 先向第一个方向移动   如果该节点可以向第二个方向移动   则尝试向第二个方向移动// 再向第二个方向移动, 如果给结点可以向第三个方向移动  则尝试向第三个方向移动// 在尝试向第三个方向移动   如果该节点为dst  则跳出循环[while的判断]  // 如果该节点不为dst  并且不可移动了   则回溯到第二个方向  继续向第二个方向移动[更新isNeedRight, isNeedUp两个标志位], 如果该节点可以向第三个方向移动, 尝试向第三个方向移动...[loop]// 如果第二个方向  不可移动了 或者超过了边界  回溯到第一个方向  继续向第一个方向移动[更新isNeedRight, isNeedUp两个标志位], 如果该节点可以向第二个方向移动, 尝试向第二个方向移动...[loop]// 如果第一个方向不可移动了 或者到了边界  返回falseprivate boolean reachInTwoUpdate(Node src, Node dst, int[]directions) {// 确保经过两次转弯if(directions.length != 3) {return false;}// 右 -> 上 -> 左// directions[0]
//      Node node = nextNode(src, Tools.RIGHT);movePath.clear();movePath.add(src);Node node = nextNode(src, directions[0]);Node tmpNode = null, tmpNode02 = null;boolean isNeedRight = true, isNeedUp = false;bigLoop:while(!node.eq(dst) ) {if(!isNeedUp) {if(tmpNode != null) {node = nextNode(tmpNode, directions[0]);}boolean isNodeMovable = true;while( (isNodeMovable=isNodeMovable(node)) ) {if(node.isInOutBounds(directions[0])) {break;} else if(node.isOutBounds(directions[0])) {return false;}if( isNodeMovableForDirection(node, directions[1]) ) {break;}movePath.add(new Node(node));node.move(directions[0]);}if(!isNodeMovable) {return false;}// 到这里说明了当前node可以向上移动了[出界 或者上面的Node可移动]isNeedUp = true;tmpNode = new Node(node);movePath.add(new Node(node));node = nextNode(node, directions[1]);}// directions[1]if(isNeedUp) {if(tmpNode02 != null) {node = nextNode(tmpNode02, directions[1]);}boolean isNodeMovable = true;while( (isNodeMovable=isNodeMovable(node)) ) {if(dst.eq(nextNode(node, directions[2]))) {movePath.add(new Node(node));movePath.add(dst);return true;}// 如果这里出界了 直接返回继续大循环向右走  因为向左走一定不会走到dst// 如果向上走走不通了   继续大循环  向右走 -> 上 -> 左if(node.isOutBounds(directions[1])) {isNeedUp = false;removeFrom(movePath, tmpNode);tmpNode02 = null;continue bigLoop;}if(isNodeMovableForDirection(node, directions[2])) {break; }movePath.add(new Node(node));node.move(directions[1]);}if(!isNodeMovable) {isNeedUp = false;isNeedRight = true;removeFrom(movePath, tmpNode);tmpNode02 = null;continue bigLoop;}// 到这里说明了当前node可以向左移动了[左面的Node可移动]isNeedUp = true;tmpNode02 = new Node(node);movePath.add(new Node(node));node = nextNode(node, directions[2]);}// directions[2]if(!isNodeMovable(node)) {continue bigLoop;}while(!node.eq(dst) ) {if(!isNodeMovable(node) || node.isOutBounds(directions[2])) {isNeedUp = true;removeFrom(movePath, tmpNode02);continue bigLoop;}movePath.add(new Node(node));node.move(directions[2]);}}if(node.eq(dst) ) {movePath.add(new Node(node));return true;}return false;}// 判断src能否沿着directions方向到达dst  经过一次转弯// 获src第一个方向上的下一个结点// 接下来的两个boolean标志 主要是用于  使下一次循环的时候  直接进入第二个方向   具体的条件 请参见代码// 先向第一个方向移动   如果该节点可以向第二个方向移动   则尝试向第二个方向移动// 在尝试向第二个方向移动   如果该节点为dst  则跳出循环[while的判断]  // 如果该节点不为dst  并且不可移动了   则回溯到第一个方向  继续向第一个方向移动[更新isNeedRight, isNeedUp两个标志位], 如果该节点可以向第二个方向移动, 尝试向第而个方向移动...[loop]// 如果第一个方向不可移动了 或者到了边界  返回falseprivate boolean reachInOneUpdate(Node src, Node dst, int[]directions) {if(directions.length != 2) {return false;}// 左 -> 上// directions[0]
//      Node node = nextNode(src, Tools.RIGHT);movePath.clear();movePath.add(src);Node node = nextNode(src, directions[0]);Node tmpNode = null;bigLoop:while(!node.eq(dst) ) {if(tmpNode != null) {node = nextNode(tmpNode, directions[0]);}// 如果出现第一个方向的下一个node本身就不可到达的情况下 直接返回falseif(!isNodeMovable(node)) {return false;}boolean isNodeMovable = true;while(!isNodeMovableForDirection(node, directions[1]) && (isNodeMovable = isNodeMovable(node)) ) {if(dst.eq(nextNode(node, directions[1]))) {movePath.add(new Node(node));movePath.add(dst);return true;}if(node.isInOutBounds(directions[0])) {break;} else if(node.isOutBounds(directions[0])) {return false;}movePath.add(new Node(node));node.move(directions[0]);}if(!isNodeMovable) {return false;}// 到这里说明了当前node可以向上移动了[出界 或者上面的Node可移动]tmpNode = new Node(node);movePath.add(new Node(node));node = nextNode(node, directions[1]);// directions[1]while(!node.eq(dst) ) {if(node.isOutBounds(directions[1]) || !isNodeMovable(node)) {removeFrom(movePath, tmpNode);continue bigLoop;}movePath.add(new Node(node));node.move(directions[1]);}}if(node.eq(dst) ) {movePath.add(new Node(node));return true;}return false;}// 从movePath2中移除tmpNode对应的结点, 以及其之后的所有结点private void removeFrom(LinkedList<Node> movePath2, Node tmpNode) {Iterator<Node> it = movePath2.iterator();while(it.hasNext()) {if(tmpNode.eq(it.next())) {it.remove();while(it.hasNext()) {it.next();it.remove();}}}}// 获取现在图片的逻辑表示  public Integer[][] getPics() {return pics;}// 获取tmpNode的direction方向的下一个结点private Node nextNode(Node tmpNode, int direction) {Node node = new Node(tmpNode);switch (direction) {case Tools.UP:node.move(Tools.UP);break;case Tools.RIGHT:node.move(Tools.RIGHT);break;case Tools.DOWN:node.move(Tools.DOWN);break;case Tools.LEFT:node.move(Tools.LEFT);break;default :throw new RuntimeException("error...");}return node;}// 判断 该节点是否可移动// 如果node在边界上  视为可移动// 如果超出边界视为  不可移动// 如果该node的数据为NULL  视为可移动private boolean isNodeMovable(Node node) {if(node.isInOutBounds()) {return true;} else if(node.isOutBounds()) {return false;}return pics[node.row][node.col] == NULL;}// 判断node的direction方向的结点  是否可移动private boolean isNodeMovableForDirection(Node node, int direction) {Node tmp = new Node(node);tmp.move(direction);return isNodeMovable(tmp);}// 判断两个结点上的数据是否相同[是否是相同的图片]public boolean isEq(Node firstNode, Node second) {return getNodeValue(firstNode) == getNodeValue(second);}// 获取移动的路径[如果两个照片能相互到达]public LinkedList<Node> getMovePath() {return movePath;}// 判断 该direction是否为正向的方向[左上, 上, 右上, 上视为正向, 其他的方向视为逆向]// 详见 canReach方法public boolean isPositiveDirection(int direction) {return direction == Tools.UP_LEFT || direction == Tools.UP || direction == Tools.UP_RIGHT || direction == Tools.RIGHT;}// 设置mainPanelpublic void setPanel(MainPanel mainPanel) {this.panel = mainPanel;}// 判断node所在的结点是否为NULLpublic boolean isNotNull(Node node) {return node.val != NULL;}// 打印日志private void logSameNodes() {for(SameNodes sn : sameNodes) {sn.print();}}public void logPics() {Log.logWithoutPosition(pics);}// 测试canReach方法public void canReachTest() {Log.log(pics);int srcRow = 5, srcCol = 0;int dstRow = 2, dstCol = 2;Node src = new Node(srcRow, srcCol);Node dst = new Node(dstRow, dstCol);System.out.println(canReach(src, dst));}// 保存"相同的图片"的所有结点信息static class SameNodes {int val;Node[] nodes;int size;public SameNodes(int val) {this.val = val;nodes = new Node[0];size = 0;}// 添加一个结点  扩容机制为原来的长度+2[因为相同的图片 必然成队出现]  更新sizepublic void add(Node node) {if(size < nodes.length) {for(int i=0; i<nodes.length; i++) {if(nodes[i]==null || !nodes[i].valid ) {nodes[i] = node;}}} else {Node[] newNodes = new Node[nodes.length + 2];System.arraycopy(nodes, 0, newNodes, 0, nodes.length);newNodes[nodes.length] = node;nodes = newNodes;}size ++;}// 移除一个结点  设置该结点的valid标志位为false  更新sizepublic void remove(Node node) {for(int i=0; i<nodes.length; i++) {if(node.eq(nodes[i])) {nodes[i].invalid();size --;}}}// 返回当前这种图片 还剩下多少张public int size() {return size;}// 是否还有图片public boolean haveNodes() {return size > 0;}// 打印日志public void print() {for(Node node : nodes) {if(node.valid) {Log.log(node);}}Log.horizon();}// 获取最后的第rank个"有效图片"[没有被移除]public int getLastTheRankValidNodeIndex(int rank) {for(int i=nodes.length-1; i>0; i--) {if(nodes[i].isValid()) {if((--rank) == 0) {return i;}}}return -1;}// 获取start位置的下一个"有效图片"[没有被移除]public int getNextValidNodeIndex(int start) {for(int i=start+1; i<nodes.length; i++) {if(nodes[i].isValid()) {return i;}}return -1;}// 返回一个迭代所有有效图片的迭代器[每次返回两个结点[图片的位置]]public PairIter pairIter() {return new PairIter();}// 遍历元素对的迭代器// 迭代所有有效图片的迭代器[每次返回两个结点[图片的位置]]class PairIter {// src, dst表示第一个结点的索引, 第二个结点的索引// lastValideNodeIndex表示最后一个有效的结点的索引// secondLastValideNodeIndex表示倒数第二个有效的结点的索引int src;int dst;int lastValideNodeIndex;int secondLastValideNodeIndex;public PairIter() {// 初始化src = getNextValidNodeIndex(-1);dst = getNextValidNodeIndex(src);lastValideNodeIndex = getLastTheRankValidNodeIndex(1);secondLastValideNodeIndex = getLastTheRankValidNodeIndex(2);}// 是否还又下一对元素public boolean hasNext() {return src >= 0;}// 返回下一对元素  更新src, dstpublic Node[] next() {      Node[] res = new Node[2];res[0] = nodes[src];res[1] = nodes[dst];// 如果dst遍历到最后一个有效的元素  更新src, dst// 否则更新dstif(dst == lastValideNodeIndex) {updateSrcWhileRemovedOrDstEnd();} else {dst = getNextValidNodeIndex(dst);}return res;}// 移除结点之后的操作// 更新lastValideNodeIndex, sencondLastValideNodeIndex// 更新src, dstpublic void updateAfterFindMatched() {updateLastValidIndex();updateSrcWhileRemovedOrDstEnd();}// 更新src, dst// 如果src为倒数第二个有效的结点   表示遍历结束   则令src为-1   返回// 更新src为src的下一个有效的结点  更新dst为src的下一个有效的结点// 如果dst为-1[如果删除了结点的情况下有可能发生]  表示src到达了lastValideNodeIndex  遍历结束  令src为-1// dst为-1    有四个结点  src遍历到2 此时2, 3匹配   删除2, 3之后, 更新src  此时src得到4, 更新dst, 此时dst就为-1private void updateSrcWhileRemovedOrDstEnd() {// 遍历完成if(src == secondLastValideNodeIndex) {src = -1;return ;}src = getNextValidNodeIndex(src);dst = getNextValidNodeIndex(src);// 遍历完成  可能某些情况下删除了元素会导致这种情况if(dst == -1) {src = -1;}}// 更新lastValideNodeIndex, secondLastValideNodeIndexprivate void updateLastValidIndex() {lastValideNodeIndex = getLastTheRankValidNodeIndex(1);secondLastValideNodeIndex = getLastTheRankValidNodeIndex(2);}}}// 保存一个结点的信息public class Node {// row, col表示该图片的行数, 列数// val 表示该图片的数据表示// valid 表示该节点是否有效[如果被移除了 则无效]int row;int col;int val;boolean valid;// 初始化public Node(int row, int col) {this.row = row;this.col = col;this.val = pics[row][col];valid = true;}public Node(Node src) {this.row = src.row;this.col = src.col;this.val = src.val;valid = true;}// 向dir方向移动public void move(int dir) { switch (dir) {case Tools.UP:row --;break;case Tools.RIGHT:col ++;break;case Tools.DOWN:row ++;break;case Tools.LEFT:col --;break;default :throw new RuntimeException("error...");}}// 返回该节点是否有效public boolean isValid() {return valid;}// 使该节点失效public void invalid() {this.valid = false;}// 判断当前结点是否等于other结点public boolean eq(Node other) {return row == other.row && col == other.col;}// 判断当前结点是否在边界上public boolean isInOutBounds() {return row == -1 || row == Tools.HEIGHT || col == -1 || col == Tools.WIDTH;}// 判断当前结点是否在direction方向上的边界上public boolean isInOutBounds(int direction) {boolean isOutBounds = false;switch (direction) {case Tools.UP:isOutBounds = row == -1;break;case Tools.RIGHT:isOutBounds = col == Tools.WIDTH;break;case Tools.DOWN:isOutBounds = row == Tools.HEIGHT;break;case Tools.LEFT:isOutBounds = col == -1;break;default :throw new RuntimeException("error...");}return isOutBounds;}// 判断当前结点是否在边界外public boolean isOutBounds() {return row < 0 || row >= Tools.HEIGHT || col < 0 || col >= Tools.WIDTH;}// 判断当前结点是否在direction方向上的边界外public boolean isOutBounds(int direction) {boolean isOutBounds = false;switch (direction) {case Tools.UP:isOutBounds = row < 0;break;case Tools.RIGHT:isOutBounds = col >= Tools.WIDTH;break;case Tools.DOWN:isOutBounds = row >= Tools.HEIGHT;break;case Tools.LEFT:isOutBounds = col < 0;break;default :throw new RuntimeException("error...");}return isOutBounds;}// 重写Object的toString方法  用于debugpublic String toString() {return "row : " + row + "  col : " + col + "  val :" + val;}}// 获取 src -> dst 的方向// 获取dst相对于src的方向public static int getDirection(Node src, Node dst) {if(src.eq(dst)) {return -1;}return Tools.getDirection(src.row, src.col, dst.row, dst.col);}}

2.2 Observer : 监听事件的接口, 接口如下 :
update(Object obj, DrawPathEvent dpe) : 当被监听者某些数据发生更新的时候, 调用

/*** file name : Observer.java* created at : 9:19:45 AM May 18, 2015* created by 970655147*/package com.hx.pictureMatching;// Observer接口
public interface Observer {// 当被监听者某些数据发生更新的时候, 调用public void update(Object obj, DrawPathEvent dpe);}// 绘制路线的Observer
class PMDrawPathObserver implements Observer {public void update(Object obj, DrawPathEvent dpe) {if(obj instanceof MainPanel) {((MainPanel)obj).handle(dpe);}}}// 提示死锁的Observer
class DeadLockObserver implements Observer {public void update(Object obj, DrawPathEvent dpe) {if(obj instanceof MainPanel) {JOptionPane.showMessageDialog((MainPanel)obj, "存在死锁!");}}}// 绘制路线的事件对象
class DrawPathEvent {// 通过的结点, 需要传递的消息private Node[] nodes;private String msg;// setter & getter// ...
}

2.3 Tools : 常量以及公共方法, 接口如下 :
generateRandomPicture(int width, int height) : 生成随机的”照片序列”
generateFromFile(String path) : 从文件中解析”照片序列”
getDirection(int srcRow, int srcCol, int dstRow, int dstCol) : 获取src 到dst应该走的方向

/*** file name : Tools.java* created at : 8:04:47 PM Apr 22, 2015* created by 970655147*/package com.hx.pictureMatching;// 工具类
public class Tools {// 各个方向常量public final static int UP = 0;public final static int RIGHT = 1;public final static int DOWN = 2;public final static int LEFT = 3;public final static int UP_LEFT = 4;public final static int UP_RIGHT = 5;public final static int DOWN_LEFT = 6;public final static int DOWN_RIGHT = 7;// 横向纵向的元素个数, 图片个数, 每一个图片占用的宽高, 距离窗口左上角的偏移public static int WIDTH = 8;public static int HEIGHT = 8;public static int PIC_NUM = 16;public static int GRID_WIDTH = 70;public static int GRID_HEIGHT = 70;public static int X_OFFSET = 70;public static int Y_OFFSET = 70;// 生成随机的"照片序列"public static Integer[][] generateRandomPicture(int width, int height) {List<Integer> al = new ArrayList<Integer>(width * height);// res[第几行][第几列]Integer[][] res = new Integer[height][width];for(int i=0; i<PIC_NUM; i++) {int num = width * height / PIC_NUM;for(int j=0; j<num; j++) {al.add(i);}}// shuffleCollections.shuffle(al);int index = al.size() - 1;for(int i=height-1; i>=0; i--) {for(int j=width-1; j>=0; j--) {res[i][j] = al.get(index--);}}// 打印日志Log.logWithoutPosition(res);return res;}// 等待用户的输入 用于debugpublic static void awaitInput() {try {System.in.read();} catch (IOException e) {e.printStackTrace();}}// 从文件中解析"照片序列"public static Integer[][] generateFromFile(String path) throws IOException {Integer[][] res = new Integer[Tools.HEIGHT][Tools.WIDTH];BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));for(int i=0; i<res.length; i++) {String line = br.readLine().trim();String[] splits = line.split("\\s+");for(int j=0; j<res.length; j++) {res[i][j] = Integer.valueOf(splits[j]);}}Log.logWithoutPosition(res);return res;}// 获取src 到dst应该走的方向public static int getDirection(int srcRow, int srcCol, int dstRow, int dstCol) {if(srcRow == dstRow) {if(srcCol < dstCol) {return Tools.RIGHT;} else {return Tools.LEFT;}} else if(srcCol == dstCol) {if(srcRow < dstRow) {return Tools.DOWN;} else {return Tools.UP;}} else if(srcRow > dstRow && srcCol > dstCol) {return Tools.UP_LEFT;} else if(srcRow > dstRow && srcCol < dstCol) {return Tools.UP_RIGHT;} else if(srcRow < dstRow && srcCol < dstCol) {return Tools.DOWN_RIGHT;} else if(srcRow < dstRow && srcCol > dstCol) {return Tools.DOWN_LEFT;}return -1;}}