[LeetCode] 529. Minesweeper 扫雷
2024-08-30 03:21:29
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.
扫雷游戏，经典的搜索问题。
1. 当点击到雷('M')时，标记为'X'，结束搜索，游戏结束。
2. 当点击到空方块('E')时，如果周围有雷，就计算雷的个数，标记为这个数字，不在搜索。如果周围没有雷的话， 标记为'B'，继续搜索8个挨着的方块。
解法1：DFS
解法2： BFS
Java: DFS
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;
}
}
Java: 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 BFS.
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;
}
}
Python:
class Solution(object):
def updateBoard(self, board, click):
"""
:type board: List[List[str]]
:type click: List[int]
:rtype: List[List[str]]
"""
q = collections.deque([click])
while q:
row, col = q.popleft()
if board[row][col] == 'M':
board[row][col] = 'X'
else:
count = 0
for i in xrange(-1, 2):
for j in xrange(-1, 2):
if i == 0 and j == 0:
continue
r, c = row + i, col + j
if not (0 <= r < len(board)) or not (0 <= c < len(board[r])):
continue
if board[r][c] == 'M' or board[r][c] == 'X':
count += 1 if count:
board[row][col] = chr(count + ord('0'))
else:
board[row][col] = 'B'
for i in xrange(-1, 2):
for j in xrange(-1, 2):
if i == 0 and j == 0:
continue
r, c = row + i, col + j
if not (0 <= r < len(board)) or not (0 <= c < len(board[r])):
continue
if board[r][c] == 'E':
q.append((r, c))
board[r][c] = ' ' return board
Python:
# Time: O(m * n)
# Space: O(m * n)
class Solution2(object):
def updateBoard(self, board, click):
"""
:type board: List[List[str]]
:type click: List[int]
:rtype: List[List[str]]
"""
row, col = click[0], click[1]
if board[row][col] == 'M':
board[row][col] = 'X'
else:
count = 0
for i in xrange(-1, 2):
for j in xrange(-1, 2):
if i == 0 and j == 0:
continue
r, c = row + i, col + j
if not (0 <= r < len(board)) or not (0 <= c < len(board[r])):
continue
if board[r][c] == 'M' or board[r][c] == 'X':
count += 1 if count:
board[row][col] = chr(count + ord('0'))
else:
board[row][col] = 'B'
for i in xrange(-1, 2):
for j in xrange(-1, 2):
if i == 0 and j == 0:
continue
r, c = row + i, col + j
if not (0 <= r < len(board)) or not (0 <= c < len(board[r])):
continue
if board[r][c] == 'E':
self.updateBoard(board, (r, c)) return board
C++:
// Time: O(m * n)
// Space: O(m + n) class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
queue<vector<int>> q;
q.emplace(click);
while (!q.empty()) {
int row = q.front()[0], col = q.front()[1];
q.pop();
if (board[row][col] == 'M') {
board[row][col] = 'X';
} else {
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 >= board.size() || c < 0 || c < 0 || c >= board[r].size()) {
continue;
}
if (board[r][c] == 'M' || board[r][c] == 'X') {
++count;
}
}
} if (count > 0) {
board[row][col] = count + '0';
} else {
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 >= board.size() || c < 0 || c < 0 || c >= board[r].size()) {
continue;
}
if (board[r][c] == 'E') {
vector<int> next_click = {r, c};
q.emplace(next_click);
board[r][c] = 'B';
}
}
}
}
}
} return board;
}
};
C++:
// Time: O(m * n)
// Space: O(m * n)
class Solution2 {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
int row = click[0], col = click[1];
if (board[row][col] == 'M') {
board[row][col] = 'X';
} else {
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 >= board.size() || c < 0 || c < 0 || c >= board[r].size()) {
continue;
}
if (board[r][c] == 'M' || board[r][c] == 'X') {
++count;
}
}
} if (count > 0) {
board[row][col] = count + '0';
} else {
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 >= board.size() || c < 0 || c < 0 || c >= board[r].size()) {
continue;
}
if (board[r][c] == 'E') {
vector<int> next_click = {r, c};
updateBoard(board, next_click);
}
}
}
}
} return board;
}
};
All LeetCode Questions List 题目汇总
最新文章
- Sage CRM 平衡区域树结构
- C语言实现单链表-02版
- Asp.Net远程调试
- 【转载】about slack
- Android Material Design:滑动指示选项卡android.support.design.widget.TabLayout的简单使用
- ylbtech-Model-Account(通用账户模块设计)
- 解决UITableView中Cell重用机制导致内容出错的方法总结
- JQuery 实现返回顶部效果
- executeBatch()相关操作汇总
- AngularJS学习笔记3
- Xadmin集成富文本编辑器ueditor
- shell ping一个IP，延时大于5，输出延时大于5s，打印输出
- 前端学习:html基础学习一
- BZOJ_2693_jzptab_莫比乌斯反演
- Python3 isdigit()方法
- Chrome 开发者工具
- There is no action xxxFun defined for api controller api/subitem
- MySQL报错： Character set ‘utf8mb4‘ is not a compiled character set and is not specified in the ‘/usr/share/mysql/charsets/Index.xml‘ file
- Google Summer of Code礼包
- poj1015陪审团——DP+路径记录
热门文章
- 【转】TUN/TAP虚拟网络设备
- re正则match、search、findall、finditer函数方法使用
- httpclient post请求中文乱码解决办法
- LeetCode 1004. Max Consecutive Ones III
- S1_搭建分布式OpenStack集群_04 keystone认证服务安装配置
- siblings() 方法
- 程序日志-应用程序-特定 权限设置并未向在应用程序容器 不可用 SID (不可用)中运行的地址 LocalHost (使用 LRPC) 中的用户 NT AUTHORITY\SYSTEM SID (S-1-5-18)授予针对 CLSID 为 {D63B10C5-BB46-4990-A94F-E40B9D520
- MongoDB 表（集合） 创建删除、数据增删改查
- 帝国cms万能标签实现标题截取后自动加入省略号的方法
- python安装redis库