题目
让我们一起来玩扫雷游戏！
给定一个代表游戏板的二维字符矩阵。?
'M'?代表一个未挖出的地雷，'E'?代表一个未挖出的空方块，'B'?代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1'?到?'8'）表示有多少地雷与这块已挖出的方块相邻，'X'?则表示一个已挖出的地雷。
如果一个地雷（'M'）被挖出，游戏就结束了-?把它改为?'X'。?
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
https://leetcode-cn.com/problems/minesweeper/
分析
这又是一道理解题目意思的难度远大于解题的题目，如果你没玩过扫雷游戏，你可能需要花费很长时间来理解，这道题很有意思，但如果面试时出这道题会不会不合适呢??
解这道题的关键是理解这个游戏，需要把它生硬的说明模拟成一次游戏操作，即有一个棋盘，玩家会点击一次某一个格子，这个时候需要你来响应他的点击操作：
当玩家点击的是雷时，直接结束游戏。
当玩家点击的是空方格时，你就帮玩家往八个方向自动探索，每往前探索一个格子就往八个方向再发散一次（剔除已走过的格子），每个方向都会直到将遇到雷时（相邻格子有一个或多个雷）结束，同时将将遇到雷的个数更新到这个格子中。
在探索格子时如果下一步没有雷，就格子设置成已挖出的空白格，即将E变成B。
理解游戏规则后再做这道题就不难了，使用广度优先算法，同时用一个状态数组来记录已走过的格子。
代码
class Solution {public char[][] updateBoard(char[][] board, int[] click) {if(board[click[0]][click[1]] == 'M'){board[click[0]][click[1]] = 'X';return board;}int[][] his = new int[board.length][board[0].length];List<int[]> list = new ArrayList<int[]>();list.add(click);bfs(list, board,his);return board;}void bfs(List<int[]> list, char[][] board, int[][] his) {if(list.size() == 0){return;}for(int[] click : list){if(board[click[0]][click[1]] == 'M'){continue;}List<int[]> nextList = new ArrayList<int[]>();his[click[0]][click[1]] = 1;//获得八个方向的雷int num = 0;num += getM(click[0] + 1, click[1], board, nextList,his);num += getM(click[0] + 1, click[1] + 1, board, nextList,his);num += getM(click[0] + 1, click[1] - 1, board, nextList,his);num += getM(click[0], click[1] - 1, board, nextList,his);num += getM(click[0], click[1] + 1, board, nextList,his);num += getM(click[0] - 1, click[1], board, nextList,his);num += getM(click[0] - 1, click[1] + 1, board, nextList,his);num += getM(click[0] - 1, click[1] - 1, board, nextList,his);if(num > 0){board[click[0]][click[1]] = (char)('0' + num);}else {board[click[0]][click[1]] = 'B';}if(num == 0){bfs( nextList, board, his);}}}int getM(int i, int j, char[][] board, List<int[]> nextList, int[][] his) {if(!inBoard(i, j, board) ){return 0;}if(his[i][j] != 1 ){int[] newClick = new int[2];newClick[0] = i;newClick[1] = j ;nextList.add(newClick);}return board[i][j] == 'M' ? 1 : 0;}boolean inBoard(int i, int j, char[][] board) {if(i>=0 && j>=0 && i<board.length && j <board[0].length){return true;}return false;}}
结果
关注个人微信公众号：肌肉码农，回复“好友”讨论问题。