Minesweeper [source code]
public class Minesweeper {
static
/******************************************************************************/
public class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length, n = board[0].length;
char[][] res = new char[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
res[i][j] = board[i][j];
int[][] mineCount = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (board[i][j] == 'M')
for (int x = -1; x < 2; x++)
for (int y = -1; y < 2; y++)
if (i + x >= 0 && i + x < m && j + y >= 0 && j + y < n && !(x == 0 && y == 0))
mineCount[i + x][j + y]++;
click(res, click, mineCount, m, n);
return res;
}
public void click(char[][] board, int[] click, int[][] mineCount, int m, int n) {
int x = click[0], y = click[1];
if (board[x][y] == 'M') {
board[x][y] = 'X';
return;
}
if (Character.isDigit(board[x][y]) || board[x][y] == 'B')
return;
if (mineCount[x][y] > 0) {
board[x][y] = (char) (mineCount[x][y] + '0');
return;
}
board[x][y] = 'B';
for (int dx = -1; dx < 2; dx++)
for (int dy = -1; dy < 2; dy++)
if (x + dx >= 0 && x + dx < m && y + dy >= 0 && y + dy < n && !(dx == 0 && dy == 0))
click(board, new int[]{x + dx, y + dy}, mineCount, m, n);
}
}
/******************************************************************************/
public static void main(String[] args) {
Minesweeper.Solution tester = new Minesweeper.Solution();
String[][] inputs = {
{"EEEEE","EEMEE","EEEEE","EEEEE"}, {"3","0"}, {"B1E1B","B1M1B","B111B","BBBBB"},
{"EEEEEEEE","EEEEEEEM","EEMEEEEE","MEEEEEEE","EEEEEEEE","EEEEEEEE","EEEEEEEE","EEMMEEEE"}, {"0", "0"}, {"BBBBBB1E","B111BB1M","12M1BB11","M211BBBB","11BBBBBB","BBBBBBBB","B1221BBB","B1MM1BBB"},
};
for (int i = 0; i < inputs.length / 3; i++) {
char[][] board = Matrix.buildFromString(inputs[3 * i]);
int[] click = new int[]{Integer.parseInt(inputs[1 + 3 * i][0]), Integer.parseInt(inputs[1 + 3 * i][1])};
char[][] ans = Matrix.buildFromString(inputs[2 + 3 * i]);
System.out.println(Printer.seperator());
String boardStr = Matrix.printMatrix(board);
String ansStr = Matrix.printMatrix(ans);
char[][] output = tester.updateBoard(board, click);
String outputStr = Matrix.printMatrix(output);
System.out.println(
Printer.wrapColor(boardStr + " AND (" + Printer.array(click) + ")" , "magenta") +
" -> " + outputStr +
Printer.wrapColor(", expected: \n" + ansStr, ansStr.equals(outputStr) ? "green" : "red")
);
}
}
}
题目比较长, 耐着性子, 细心点, 图文对照好好读懂; 题目长的一般不见得最后会很难, 但是读懂题目往往是这种题目的关键;
题目给了例子, 那么首先先人逻辑理解一下到底是怎么跑的;
不知道为什么LeetCode上面这个题目downvote这么多, 我感觉这个题目还挺有意思的?
感觉这个问题真正如果想要作为一个难题, 那么开始题目的那四条rule就不告诉我们, 这个题目就真的难了;
另外这个题目在tag上, DFS和BFS都有, 最后实际上哪种更好呢? 在写代码和跑人逻辑的过程中, 我发现我感觉好像是DFS更好;
最后的速度是13ms (11%), 这个慢的有点出乎意料. 按理说我其实还加了一个优化的: 所有的有数字的entry, 我都提前把这些数字全都计算处理啊, 这样不用在DFS的时候再去计算;
感觉好像可能是我的预处理太浪费时间了, discussion的最优解的DFS版本直接就是一个函数, 没有写helper;
另外这个题目还是体现了我自己的基础薄弱, 其实非常简单的一个题目, 但是写的时候还是各种bug调不出来;
discussion有一个很好的解:
This is a typical Search problem, either by using DFS or BFS. Search rules:
- If click on a mine ('M'), mark it as 'X', stop further search.
- If click on an empty cell ('E'), depends on how many surrounding mine:
- Has surrounding mine(s), mark it with number of surrounding mine(s), stop further search.
- No surrounding mine, mark it as 'B', continue search its 8 neighbors.
DFS solution.
public class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length, n = board[0].length;
int row = click[0], col = click[1];
if (board[row][col] == 'M') { // Mine
board[row][col] = 'X';
}
else { // Empty
// Get number of mines first.
int count = 0;
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'M' || board[r][c] == 'X') count++;
}
}
if (count > 0) { // If it is not a 'B', stop further DFS.
board[row][col] = (char)(count + '0');
}
else { // Continue DFS to adjacent cells.
board[row][col] = 'B';
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'E') updateBoard(board, new int[] {r, c});
}
}
}
}
return board;
}
}
这个解看完了之后, 意识到我的解法的一个问题; 我把counts全都提前计算出来了, 这个看起来是一个precomputation, 但是实际上这个有一个隐患: 我们这个题目做的其实只是一个click的update, 所以你实际上是未必需要用到所有的counts的; 事实上, 这个precompute最后造成的速度损失相当巨大;
另外我这个题目之所以选择用void helper的方法做, 是因为我看到这个主函数需要一个返回值, 那么我的想法是尽量不要改变board本身的entry, 而是专门做一个res来更新(严格来说, 我这个还是算是O(1) extra space的). 所以helper本身直接用mutation来完成操作就行了;
他这个操作实际上跟我的最后主要的区别就是是否mutate the input. 至于速度上面, 看起来好像他的方法board不停的被传递, 但是实际上, 因为array本身其实也是一个object, 所以被传递的始终就是一个指针而已, 几乎没有任何的penalty;
他这里在计算count的时候还考虑了X, 我认为是不必要的, 这种情况不可能出现: 有X就已经结束了;
他这个先计算count, 然后再决定是否recurse down的想法还是有点意思的;
总体来说DFS解法确实是比较简单的;
这个DFS是很快的, 算是submission最优解, 6(72);
BFS solution. As you can see the basic logic is almost the same as DFS. Only added a queue to facilitate BFS.
public class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length, n = board[0].length;
Queue<int[]> queue = new LinkedList<>();
queue.add(click);
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int row = cell[0], col = cell[1];
if (board[row][col] == 'M') { // Mine
board[row][col] = 'X';
}
else { // Empty
// Get number of mines first.
int count = 0;
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'M' || board[r][c] == 'X') count++;
}
}
if (count > 0) { // If it is not a 'B', stop further DFS.
board[row][col] = (char)(count + '0');
}
else { // Continue BFS to adjacent cells.
board[row][col] = 'B';
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'E') {
queue.add(new int[] {r, c});
board[r][c] = 'B'; // Avoid to be added again.
}
}
}
}
}
}
return board;
}
}
正如他自己所说, 他这里这个BFS其实是非常trivial的一个改写, 就是对上面的DFS做法的一个简单的翻译而已. 但是实际上还是完成了一个BFS的过程;
you can set board[r][c] = 'B' after adding it to queue to avoid using visited array.
这个是一个改进(上面这个代码已经改过来了); 其实只要保证你走到一个entry的时候合理更新了之后, 就不会出现重复的问题; 其他的entry就算后来又往这个entry发来call, 也会立刻return;
另外, 如果真的让你写BFS, 你真的写的出来吗? 其实没有explicit的node的BFS, 我好像并没有写过? 这种问题设计的时候的核心问题, 其实是你的queue里面放的是什么; 当然了, 作为recursion来理解, 我们认为肯定是放的是call的参数; 不过要具体问题具体分析: 这里的哪个参数可以最简短的反映一个subproblem;
这个BFS最后并不快, 12ms左右好像;
这个是另外一个BFS:
public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length;
if (m == 0) return board;
int n = board[0].length;
int[][] dir = {{-1, 0},{-1, 1},{0, 1},{1,1},{1, 0},{1, -1},{0, -1}, {-1, -1}};
int X = 0, Y = 0, newX = 0, newY = 0, cnt = 0;
Queue<int[]> q1 = new LinkedList<>();
Queue<int[]> q2 = new LinkedList<>();
q1.offer(click);
while (!q1.isEmpty()) {
X = q1.peek()[0]; Y = q1.poll()[1];
switch (board[X][Y]) {
case 'M' :
board[X][Y] = 'X';
return board;
case 'E' :
cnt = 0;
q2.clear();
for (int i = 0; i < 8; i++) {
newX = X + dir[i][0];
newY = Y + dir[i][1];
if (0 <= newX && newX < m && 0 <= newY && newY < n) {
if (board[newX][newY] == 'M') cnt++;
if (board[newX][newY] == 'E') q2.offer(new int[]{newX, newY});
}
}
if (cnt == 0) {
board[X][Y] = 'B';
q1.addAll(q2);
} else board[X][Y] = Character.forDigit(cnt, 10);
break;
}
}
return board;
}
这里他q2其实就是用来保存当前的node对于下一个level的contribution; 其实对于算法本身好像没有太大的影响?
虽然一般我们常见的BFS的循环其实都是两层的(一层on queue, 一层on level), 但是这里确实不需要做这个工作, 因为这里并不需要这个level的概念好像, 所以直接loop on queue就行了;
注意他这里用一个数组把(dx, dy)保存下来, 这个其实是一个不错的办法, 而且可以说使整个代码更加compact: 所以小的循环当iterator复杂的时候可以尝试直接enumerate出来?
discussion好像也没有什么其他的特别有新意的解法了;
submission好像也没有什么惊喜了;
Problem Description
Let's play the minesweeper game (Wikipedia, online game)!
You are given a 2D char matrix representing the game board. 'M' represents an unrevealed mine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine.
Now given the next click position (row and column indices) among all the unrevealed squares ('M' or 'E'), return the board after revealing this position according to the following rules:
- If a mine ('M') is revealed, then the game is over - change it to 'X'.
- If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
- If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
- Return the board when no more squares will be revealed.
Example 1:
Input:
[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]
Click : [3,0]
Output:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Explanation:
Example 2:
Input:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
Output:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'X', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Explanation:
Note:
- The range of the input matrix's height and width is [1,50].
- The click position will only be an unrevealed square ('M' or 'E'), which also means the input board contains at least one clickable square.
- The input board won't be a stage when game is over (some mines have been revealed).
- For simplicity, not mentioned rules should be ignored in this problem. For example, you don't need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.
Difficulty:Medium
Total Accepted:8.7K
Total Submissions:17.5K
Contributor: fallcreek
Companies
amazon
Related Topics
depth-first search breadth-first search