07 扫雷

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

1. 前言

这是在做了连连看的自动分析连连看的各个可以连接的图片之后, 突然看到了连连看的这个界面似乎和扫雷的界面有点相似, 所以后来就有了一些兴趣,,

备注 : 解析[parse按钮] 所有未翻动的方格是雷的概率的的计算存在一个bug[如果能够确定一个方格必然为雷的话, 会影响该方格影响的其他方格[已翻开]旁边未翻开的方格的概率]

难点主要在于对于四个方向上的四边和中心的其他方块单独处理, 也不叫难, 算是烦吧

元素介绍 :
亮灰色的块状方格 : 未翻动的方格
深灰色的块状方格 : 旁边八个方格均没有雷的方格
带数字的方格 : 数字表示旁边的八个空格中地雷的个数
棋子标志的方格 : 用户确定该方格是雷的标记
问号标记的方格 : 用户觉得该方格可能是雷的标记
这里写图片描述

2. 基本的数据结构介绍

2.1 MineMap : 整个游戏的核心Model, 其接口如下 :
click(int row, int col) : 响应点击事件, 更新model
clickedTheMine() : 如果点中了地雷则显示所有的数据
getSurfaces() : 获取surface 用于mainPanel中绘制图片
isFindAllMine() : 是否找到了所有的雷
isOutBounds(int row, int col) : 判断row, col是否越界
parse() : 分析数据分析可分析的未翻开的方格是地雷的概率
rSKClick(int row, int col) : 处理鼠标右键的事件 CONVERED FLAG QUESTION轮流切换并且记录flagedNodes

/*** file name : MineMap.java* created at : 10:16:41 AM May 18, 2015* created by 970655147*/package com.hx.mineSweeper;public class MineMap {// 地图分布, 以及外观的物理表示private Integer[][] map;private Integer[][] surface;// 记录以确定的结点 的旁边的未确定的结点时地雷的概率, 该结点是地雷的概率[取周围未确定的结点判定当前结点为地雷的概率的最大值]private int[][] probabilityAround;private int[][] probability;// frame 表示整个显示的窗口  用于更新计分private Frame frame;// 被标记的Node  用于计算用户的标记是否正确private List<Node> flagedNodes;// 总共的地雷的数目, 以及未翻开的Node的数目private int mineSum;private int unconvered;// 初始化public MineMap() {}public MineMap(Integer[][] map, int mineSum) {this.map = map;surface = new Integer[map.length][map[0].length];probability = new int[map.length][map[0].length];probabilityAround = new int[map.length][map[0].length];flagedNodes = new LinkedList<Node>();init(mineSum);}// 初始化 清空surfaceprivate void init(int mineSum) {this.mineSum = mineSum;unconvered = map.length * map[0].length;flagedNodes.clear();for(int row=0; row<surface.length; row++) {for(int col=0; col<surface[0].length; col++) {surface[row][col] = Tools.CONVERED;}}}public void setFrame(Frame frame) {this.frame = frame;}// 鼠标左键点击处理// 如果该Node是地雷[数据为-1]  报告游戏结束// 否则 如果该方格的数据不为0[则必定为1-8]  显示该方格的数据// 否则  如果该方格未翻开[该方格的数据必定为0]  显示该方格的数据  因为数据为0  所以显示该方格周围所有的为0的方格的数据public boolean click(int row, int col) {if(map[row][col] == Tools.MINE) {return true;} else if(map[row][col] != Tools.NONE) {unconvered --;surface[row][col] = map[row][col];} else {if(isNodeUnjudgeable(surface, row, col)) {unconvered --;surface[row][col] = map[row][col];showZeroAround(row, col);}}return false;}// 如果点中了地雷  则显示所有的数据public void clickedTheMine() {for(int row=0; row<map.length; row++) {for(int col=0; col<map[0].length; col++) {surface[row][col] = map[row][col];}}}// 处理鼠标右键的事件  CONVERED FLAG QUESTION轮流切换  并且记录flagedNodespublic void rSKClick(int row, int col) {// need to deal by Observer, omit it,,if(surface[row][col] == Tools.CONVERED) {surface[row][col] = Tools.FLAG;flagedNodes.add(new Node(row, col));frame.incOrDecRest(false);} else if(surface[row][col] == Tools.FLAG) {surface[row][col] = Tools.QUESTION;flagedNodes.remove(new Node(row, col));frame.incOrDecRest(true);           } else if(surface[row][col] == Tools.QUESTION) {surface[row][col] = Tools.CONVERED;}Log.log(flagedNodes);}// 显示该方格各个方向上的数据// 如果 某个周围的方格的数据不为0  则直接显示该方格的数据// 如果 某个周围的方格的数据为0 则显示该方格的数据的同时  在去翻开该方格的周围的方格private void showZeroAround(int row, int col) {for(int direction : Tools.ALL_DIRECTIONS) {int row02 = 0, col02 = 0;switch(direction) {case Tools.LEFT:row02 = row; col02 = col-1;break;case Tools.UP:row02 = row-1; col02 = col;break;case Tools.RIGHT:row02 = row; col02 = col+1;break;case Tools.DOWN:row02 = row+1; col02 = col;break;}if(!isOutBounds(row02, col02)) {                if(surface[row02][col02] == Tools.CONVERED) {   unconvered --;surface[row02][col02] = map[row02][col02];if(map[row02][col02] == Tools.NONE) {showZeroAround(row02, col02);}}}}}// 判断row, col是否越界public boolean isOutBounds(int row, int col) {return row<0 || col<0 || row>=map.length || col>=map[0].length;}// 获取surface  用于mainPanel中绘制图片public Integer[][] getSurfaces() {return surface;}// 打印map中的数据public void logMap() {Log.log(map);}// 更新mappublic void setMap(Integer[][] map, int mineSum) {this.map = map;init(mineSum);}// 分析数据  分析可分析的未翻开的方格是地雷的概率 // 先计算出可以判别的结点的周围的不可判别的结点是 地雷的概率// 在计算该节点 周围判定当前结点是地雷概率最高的那个// 注 : 这是一种最粗略的分析, 有空的话  以后再完善public int[][] parse() {int rowEnd = surface.length - 1;int colEnd = surface[0].length - 1;// 先清空 probability中的数据 以免上一次的结果影响这一次的结果[以为不确定的结点不会计算]// 先计算出可以判别的结点的周围的不可判别的结点是 地雷的概率clearProbability();calcProbabilityAround(surface);// 计算四个角落上的四个结点[计算三个结点]calc4Corner(surface);// 计算四个边上的((rowEnd + colEnd) *　2 - 4)个结点[计算五个结点]for(int i=1; i<rowEnd; i++) {if(surface[0][i] < Tools.NONE) {    probability[0][i] = getRowSideProb(surface, 0, i-1, 2, 2, 1, i-1, 1, 3);}if(surface[rowEnd][i] < Tools.NONE) {probability[rowEnd][i] = getRowSideProb(surface, rowEnd, i-1, 2, 2, rowEnd-1, i-1, 1, 3);}}for(int i=1; i<colEnd; i++) {if(surface[i][0] < Tools.NONE) {    probability[i][0] = getColSideProb(surface, 0, i-1, 2, 2, 1, i-1, 1, 3);}if(surface[i][colEnd] < Tools.NONE) {probability[i][colEnd] = getColSideProb(surface, colEnd, i-1, 2, 2, colEnd-1, i-1, 1, 3);}}// 计算其他的结点[计算9个结点]for(int row=1; row<rowEnd; row++) {for(int col=1; col<colEnd; col++) {if(surface[row][col] < Tools.NONE) {probability[row][col] = getNormalGridProb(surface, row, col);}}}return probability;}// 清空probability中的数据private void clearProbability() {for(int row=0; row<probability.length; row++) {for(int col=0; col<probability[0].length; col++) {probability[row][col] = 0;}}   }// 计算四个角落的probabilityprivate void calc4Corner(Integer[][] surface) {int rowEnd = surface.length - 1;int colEnd = surface[0].length - 1;if(surface[0][0] < Tools.NONE) { int rows[] = new int[]{0, 1, 1};int cols[] = new int[]{1, 0, 1};probability[0][0] = getCornerProb(surface, rows, cols);}if(surface[0][colEnd] < Tools.NONE) { int rows[] = new int[]{0, 1, 1};int cols[] = new int[]{colEnd-1, colEnd, colEnd-1};probability[0][colEnd] = getCornerProb(surface, rows, cols);}// ... 这两个地方没有改 害得我调试了半天if(surface[rowEnd][colEnd] < Tools.NONE) { int rows[] = new int[]{rowEnd, rowEnd-1, rowEnd-1};int cols[] = new int[]{colEnd-1, colEnd, colEnd-1};probability[rowEnd][colEnd] = getCornerProb(surface, rows, cols);}if(surface[rowEnd][0] < Tools.NONE) { int rows[] = new int[]{rowEnd-1, rowEnd, rowEnd-1};int cols[] = new int[]{0, 1, 1};probability[rowEnd][0] = getCornerProb(surface, rows, cols);}}// assistMethodprivate int getCornerProb(Integer[][] surface, int[] rows, int[] cols) {int num = 0;// 获取周围的几个结点中判定当前结点为地雷的概率中的最低的一个for(int i=0; i<rows.length; i++) {if(probabilityAround[rows[i]][cols[i]] > num) {num = probabilityAround[rows[i]][cols[i]];}}return num;}// assistMethodprivate int getRowSideProb(Integer[][] surface, int row01, int start01, int step01, int loopNum01, int row02, int start02, int step02, int loopNum02) {int num = 0;for(int i=0; i<loopNum01; i++) {if(probabilityAround[row01][start01] > num) {num = probabilityAround[row01][start01];}start01 += step01;}for(int i=0; i<loopNum02; i++) {if(probabilityAround[row02][start02] > num) {num = probabilityAround[row02][start02];}start02 += step02;}return num;}// assistMethodprivate int getColSideProb(Integer[][] surface, int col01, int start01, int step01, int loopNum01, int col02, int start02, int step02, int loopNum02) {int num = 0;for(int i=0; i<loopNum01; i++) {if(probabilityAround[start01][col01] > num) {num = probabilityAround[start01][col01];}start01 += step01;}for(int i=0; i<loopNum02; i++) {if(probabilityAround[start02][col02] > num) {num = probabilityAround[start02][col02];}start02 += step02;}return num;}// assistMethodprivate int getNormalGridProb(Integer[][] surface, int row, int col) {int num = 0;for(int i=-1; i<2; i++) {if(probabilityAround[row-1][col+i] > num) {num = probabilityAround[row-1][col+i];}if(probabilityAround[row+1][col+i] > num) {num = probabilityAround[row+1][col+i];}   }for(int i=-1; i<2; i+=2) {if(probabilityAround[row][col+i] > num) {num = probabilityAround[row][col+i];}}return num;}// 计算每一个翻开的方格 其周围未翻开的方格是地雷的概率private void calcProbabilityAround(Integer[][] surface) {for(int row=0; row<surface.length; row++) {for(int col=0; col<surface[0].length; col++) {probabilityAround[row][col] = getProb(surface, row, col);}}}// 计算row, col的方格 其周围未翻开的方格是地雷的概率// 如果该方格未翻开 直接返回0// 否则  对该Node是否在边界上  分别分析[分析的方式不相同]private int getProb(Integer[][] surface, int row, int col) {int prob = 0;if(isNodeUnjudgeable(surface, row, col)) {prob = 0;} else {if(isInBounds(row, col)) {prob = getGridInBoundsProb(surface, row, col);} else {prob = getNormalGridProb1(surface, row, col);}}return prob;}// 分析在边界上的方格 // 先分析row, col是否是四个角落的方格  如果是 则计算结果[3个结点] 返回// 否则  计算结果[5个结点]  返回private int getGridInBoundsProb(Integer[][] surface, int row, int col) {int rowEnd = surface.length - 1;int colEnd = surface[0].length - 1;boolean is4Corner = false;int num = 0;if(row == 0 && col == 0) {is4Corner = true;int rows[] = new int[]{0, 1, 1};int cols[] = new int[]{1, 0, 1};num = getCornerProb1(surface, rows, cols);} else if(row == 0 && col == colEnd) {is4Corner = true;int rows[] = new int[]{0, 1, 1};int cols[] = new int[]{colEnd-1, colEnd, colEnd-1};num = getCornerProb1(surface, rows, cols);} else if(row == rowEnd && col == colEnd) {is4Corner = true;int rows[] = new int[]{rowEnd, rowEnd-1, rowEnd-1};int cols[] = new int[]{colEnd-1, colEnd, colEnd-1};num = getCornerProb1(surface, rows, cols);} else if(row == rowEnd && col == 0) {is4Corner = true;int rows[] = new int[]{rowEnd-1, rowEnd, rowEnd-1};int cols[] = new int[]{0, 1, 1};num = getCornerProb1(surface, rows, cols);}// 计算四个角落的四个结点if(is4Corner) {return getProbByNum(num, surface[row][col]);// 计算边界上 出去四个角落的四个结点的其他结点} else {if(row == 0) {num = getRowSideProb1(surface, 0, col-1, 2, 2, 1, col-1, 1, 3);} else if(row == rowEnd) {num = getRowSideProb1(surface, rowEnd, col-1, 2, 2, rowEnd-1, col-1, 1, 3);}if(col == 0) {num = getColSideProb1(surface, 0, row-1, 2, 2, 1, row-1, 1, 3);} else if(col == colEnd) {num = getColSideProb1(surface, colEnd, row-1, 2, 2, colEnd-1, row-1, 1, 3);}return getProbByNum(num, surface[row][col]);}}// assistMethodprivate int getCornerProb1(Integer[][] surface, int[] rows, int[] cols) {int num = 0;for(int i=0; i<rows.length; i++) {if(isNodeUnjudgeable(surface, rows[i], cols[i])) {num ++;}}return num;}// assistMethodprivate int getRowSideProb1(Integer[][] surface, int row01, int start01, int step01, int loopNum01, int row02, int start02, int step02, int loopNum02) {int num = 0;for(int i=0; i<loopNum01; i++) {if(isNodeUnjudgeable(surface, row01, start01)) {num ++;}start01 += step01;}for(int i=0; i<loopNum02; i++) {if(isNodeUnjudgeable(surface, row02, start02)) {num ++;}start02 += step02;}return num;}// assistMethodprivate int getColSideProb1(Integer[][] surface, int col01, int start01, int step01, int loopNum01, int col02, int start02, int step02, int loopNum02) {int num = 0;for(int i=0; i<loopNum01; i++) {if(isNodeUnjudgeable(surface, start01, col01)) {num ++;}start01 += step01;}for(int i=0; i<loopNum02; i++) {if(isNodeUnjudgeable(surface, start02, col02)) {num ++;}start02 += step02;}return num;}// assistMethodprivate int getNormalGridProb1(Integer[][] surface, int row, int col) {int num = 0;for(int i=-1; i<2; i++) {if(isNodeUnjudgeable(surface, row-1, col+i)) {num ++;}if(isNodeUnjudgeable(surface, row+1, col+i)) {num ++;}   }for(int i=-1; i<2; i+=2) {if(isNodeUnjudgeable(surface, row, col+i)) {num ++;}}return getProbByNum(num, surface[row][col]);}// 通过 旁边剩下的未翻开的方格的个数, 和该位置的数据  分析未翻开的方格是地雷的概率[百分制]private int getProbByNum(int num, int all) {if(num == 0 || all < Tools.NONE) {return 0;}return (all * 100) / num;}// 是否row, col在边界上private boolean isInBounds(int row, int col) {return row == 0 || row == (map.length-1) || col == 0 || col == (map[0].length-1);}// 是否row, col所在的方格未翻开private boolean isNodeUnjudgeable(Integer[][] surface, int row, int col) {return surface[row][col] <= Tools.CONVERED;}// 是否找到了所有的地雷public boolean isFindAllMine() {return unconvered == mineSum;}// Nodestatic class Node {int row;int col;public Node() {super();}public Node(int row, int col) {this.row = row;this.col = col;}@Overridepublic boolean equals(Object other) {if(other == this) {return true;}if(!(other instanceof Node) ) {return false;}Node otherNode = (Node) other;return this.row == otherNode.row && this.col == otherNode.col;}public String toString() {return "row : " + row + "  col : " + col;}}}

2.2 Tools : 工具类, 用于存放常量, 和一些公共方法
generateMineMap(int width, int height, Integer[] mines) : 生成一个扫雷的地图Model
allDirectionsBut(int direction) : 返回除了给定的direction之外的其他方向
contains(Integer[] intArr, int size, int val) : 判断intArr[0-size]中是否包含值为val的数字
generateFromFile(String path) : 从文件中解析”照片序列”
generateRandomMine(int range, int size) : 生成随机的”地雷序列”

/*** file name : Tools.java* created at : 8:04:47 PM Apr 22, 2015* created by 970655147*/package com.hx.mineSweeper;// 工具类
public class Tools {// 常量 一个方格的各种状态的标记public static final int QUESTION = -4;public static final int FLAG = -3;public static final int CONVERED = -2;public static final int MINE = -1;public static final int NONE = 0;public static final int ONE = 1;public static final int TWO = 2;public static final int THREE = 3;public static final int FOUR = 4;public static final int FIVE = 5;public static final int SIX = 6;public static final int SEVEN = 7;public static final int EIGHT = 8;// 四个方向public static final int UP = 0;public static final int RIGHT = 1;public static final int DOWN = 2;public static final int LEFT = 3;public static final int[] ALL_DIRECTIONS = {UP, RIGHT, DOWN, LEFT};// 图片的个数, 方格/ 图片 的宽高等等// 地图显示 的横向, 纵向 偏移public static int PIC_NUM = 13;public static int WIDTH = 10;public static int HEIGHT = 10;public static int GRID_WIDTH = (Frame.FRAMEHEIGHT - 100) / WIDTH;public static int GRID_HEIGHT = (Frame.FRAMEHEIGHT - 100) / HEIGHT;public static int X_OFFSET = 30;public static int Y_OFFSET = 30;// 雷的个数, 雷的id的范围public static int SIZE = (WIDTH * HEIGHT) / 10;public static int RANGE = WIDTH * HEIGHT;// 生成随机的"地雷序列"public static Integer[] generateRandomMine(int range, int size) {Random ran = new Random();Integer[] res = new Integer[size];int idx = 0;while(idx < size) {int n = ran.nextInt(range);if(!contains(res, idx, n)) {res[idx ++] = n;}}return res;}// 生成一个扫雷的地图Modelpublic static Integer[][] generateMineMap(int width, int height, Integer[] mines) {// height行  width列Integer[][] res = new Integer[height][width];for(int row=0; row<res.length; row++) {for(int col=0; col<res[0].length; col++) {res[row][col] = 0;}}for(int i=0; i<mines.length; i++) {res[getRowByPos(mines[i], width)][getColByPos(mines[i], width)] = MINE;}initRes(res);return res;}// 计算各个方格的数字private static void initRes(Integer[][] res) {int rowEnd = res.length - 1;int colEnd = res[0].length - 1;// 初始化四个角落上的四个结点[计算三个结点]init4Corner(res);// 初始化四个边上的((rowEnd + colEnd) *　2 - 4)个结点[计算五个结点]for(int i=1; i<rowEnd; i++) {if(res[0][i] != MINE) { res[0][i] = getRowSideSize(res, 0, i-1, 2, 2, 1, i-1, 1, 3);}if(res[rowEnd][i] != MINE) {res[rowEnd][i] = getRowSideSize(res, rowEnd, i-1, 2, 2, rowEnd-1, i-1, 1, 3);}}for(int i=1; i<colEnd; i++) {if(res[i][0] != MINE) { res[i][0] = getColSideSize(res, 0, i-1, 2, 2, 1, i-1, 1, 3);}if(res[i][colEnd] != MINE) {res[i][colEnd] = getColSideSize(res, colEnd, i-1, 2, 2, colEnd-1, i-1, 1, 3);}}// 计算其他的结点[计算9个结点]for(int row=1; row<rowEnd; row++) {for(int col=1; col<colEnd; col++) {if(res[row][col] != MINE) {res[row][col] = getNormalGridSize(res, row, col);}}}}private static int getRowSideSize(Integer[][] res, int row01, int start01, int step01, int loopNum01, int row02, int start02, int step02, int loopNum02) {int num = 0;for(int i=0; i<loopNum01; i++) {if(res[row01][start01] == MINE) {num ++;}start01 += step01;}for(int i=0; i<loopNum02; i++) {if(res[row02][start02] == MINE) {num ++;}start02 += step02;}return num;}private static int getColSideSize(Integer[][] res, int col01, int start01, int step01, int loopNum01, int col02, int start02, int step02, int loopNum02) {int num = 0;for(int i=0; i<loopNum01; i++) {if(res[start01][col01] == MINE) {num ++;}start01 += step01;}for(int i=0; i<loopNum02; i++) {if(res[start02][col02] == MINE) {num ++;}start02 += step02;}return num;}private static int getNormalGridSize(Integer[][] res, int row, int col) {int num = 0;for(int i=-1; i<2; i++) {if(res[row-1][col+i] == MINE) {num ++;}if(res[row+1][col+i] == MINE) {num ++;}   }for(int i=-1; i<2; i+=2) {if(res[row][col+i] == MINE) {num ++;}}return num;}private static void init4Corner(Integer[][] res) {int rowEnd = res.length - 1;int colEnd = res[0].length - 1;if(res[0][0] != MINE) { int rows[] = new int[]{0, 1, 1};int cols[] = new int[]{1, 0, 1};res[0][0] = getCornerSize(res, rows, cols);}if(res[0][colEnd] != MINE) { int rows[] = new int[]{0, 1, 1};int cols[] = new int[]{colEnd-1, colEnd, colEnd-1};res[0][colEnd] = getCornerSize(res, rows, cols);}// ... 这两个地方没有改 害得我调试了半天if(res[rowEnd][colEnd] != MINE) { int rows[] = new int[]{rowEnd, rowEnd-1, rowEnd-1};int cols[] = new int[]{colEnd-1, colEnd, colEnd-1};res[rowEnd][colEnd] = getCornerSize(res, rows, cols);}if(res[rowEnd][0] != MINE) { int rows[] = new int[]{rowEnd-1, rowEnd, rowEnd-1};int cols[] = new int[]{0, 1, 1};res[rowEnd][0] = getCornerSize(res, rows, cols);}}private static Integer getCornerSize(Integer[][] res, int[] rows, int[] cols) {int num = 0;for(int i=0; i<rows.length; i++) {if(res[rows[i]][cols[i]] == MINE) {num ++;}}return num;}public static int getRowByPos(int pos, int width) {return pos / width;}public static int getColByPos(int pos, int width) {return pos % width;}// 判断intArr[0-size]中是否包含值为val的数字public static boolean contains(Integer[] intArr, int size, int val) {for(int i=0; i<size; i++) {if(intArr[i] == val) {return true;}}return false;}// 等待用户的输入 用于debugpublic static void awaitInput() {try {System.in.read();} catch (IOException e) {e.printStackTrace();}}// 返回除了给定的direction之外的其他方向public static int[] allDirectionsBut(int direction) {int[] directions = new int[3];int idx = 0;for(int dir : ALL_DIRECTIONS) {if(dir != direction) {directions[idx ++] = dir;}}return directions;}// 从文件中解析"照片序列"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;}}