Minesweeper – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Let’s play the minesweeper game (Wikipedia, online game)!
You are given an m x n char matrix board representing the game board where:
'M'represents an unrevealed mine,'E'represents an unrevealed empty square,'B'represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),- digit (
'1'to'8') represents how many mines are adjacent to this revealed square, and 'X'represents a revealed mine.
You are also given an integer array click where click = [clickr, clickc] represents the next click position 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. You should change it to'X'. - If an empty square
'E'with no adjacent mines is revealed, then change it to a 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: board = [["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"]]
Example 2:
Input: board = [["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"]]
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 50board[i][j]is either'M','E','B', or a digit from'1'to'8'.click.length == 20 <= clickr < m0 <= clickc < nboard[clickr][clickc]is either'M'or'E'.
C++ Minesweeper LeetCode Solution
class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
if(board[click[0]][click[1]] == 'M'){
board[click[0]][click[1]] = 'X';
return board;
}
reveal(board,click[0],click[1]);
return board;
}
bool inboard(const vector<vector<char>>& board, int x, int y){
return ( x>=0 && x<board.size() && y>=0 && y<board[0].size() );
}
void reveal(vector<vector<char>>& board, int x, int y){
if(!inboard(board,x,y)) return;
if(board[x][y] == 'E'){
//search 8 adjacent squares
int count = 0;
if(inboard(board,x-1,y-1) && board[x-1][y-1] == 'M') count++;
if(inboard(board,x-1,y ) && board[x-1][y ] == 'M') count++;
if(inboard(board,x-1,y+1) && board[x-1][y+1] == 'M') count++;
if(inboard(board,x ,y-1) && board[x ][y-1] == 'M') count++;
if(inboard(board,x ,y+1) && board[x ][y+1] == 'M') count++;
if(inboard(board,x+1,y-1) && board[x+1][y-1] == 'M') count++;
if(inboard(board,x+1,y ) && board[x+1][y ] == 'M') count++;
if(inboard(board,x+1,y+1) && board[x+1][y+1] == 'M') count++;
if(count>0)
board[x][y] = '0'+count;
else{
board[x][y] = 'B';
reveal(board,x-1,y-1);
reveal(board,x-1,y );
reveal(board,x-1,y+1);
reveal(board,x ,y-1);
reveal(board,x ,y+1);
reveal(board,x+1,y-1);
reveal(board,x+1,y );
reveal(board,x+1,y+1);
}
}
}
};
Java Minesweeper LeetCode Solution
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;
}
}
Python 3 Minesweeper LeetCode Solution
class Solution(object):
def updateBoard(self, board, click):
"""
:type board: List[List[str]]
:type click: List[int]
:rtype: List[List[str]]
"""
if not board:
return []
m, n = len(board), len(board[0])
i, j = click[0], click[1]
# If a mine ('M') is revealed, then the game is over - change it to 'X'.
if board[i][j] == 'M':
board[i][j] = 'X'
return board
# run dfs to reveal the board
self.dfs(board, i, j)
return board
def dfs(self, board, i, j):
if board[i][j] != 'E':
return
m, n = len(board), len(board[0])
directions = [(-1,-1), (0,-1), (1,-1), (1,0), (1,1), (0,1), (-1,1), (-1,0)]
mine_count = 0
for d in directions:
ni, nj = i + d[0], j + d[1]
if 0 <= ni < m and 0 <= nj < n and board[ni][nj] == 'M':
mine_count += 1
if mine_count == 0:
board[i][j] = 'B'
else:
board[i][j] = str(mine_count)
return
for d in directions:
ni, nj = i + d[0], j + d[1]
if 0 <= ni < m and 0 <= nj < n:
self.dfs(board, ni, nj)
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
