LN : leetcode 529 Minesweeper
2024-08-30 21:34:58
lc 529 Minesweeper
Let's play the minesweeper 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.
递归 Accepted##
扫雷游戏,其实还挺简单的,注意判断是否在版图之内,利用递归不断推算并且更新。
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;
}
int out(vector<vector<char>>& board, int x, int y) {
return (x < 0 || y < 0 || x >= board.size() || y >= board[0].size());
}
void reveal(vector<vector<char>>& board, int x, int y) {
if (out(board, x, y)) return;
if (board[x][y] == 'E') {
int m = 0;
if (!out(board, x-1, y-1) && board[x-1][y-1] == 'M') m++;
if (!out(board, x-1, y) && board[x-1][y] == 'M') m++;
if (!out(board, x-1, y+1) && board[x-1][y+1] == 'M') m++;
if (!out(board, x, y-1) && board[x][y-1] == 'M') m++;
if (!out(board, x, y+1) && board[x][y+1] == 'M') m++;
if (!out(board, x+1, y-1) && board[x+1][y-1] == 'M') m++;
if (!out(board, x+1, y+1) && board[x+1][y+1] == 'M') m++;
if (!out(board, x+1, y) && board[x+1][y] == 'M') m++;
if (m) {
board[x][y] = '0'+m;
} 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+1);
reveal(board, x+1, y);
}
}
}
};
最新文章
- linux下可执行程序的装载和启动
- 修改CMD字符编码
- 如何使用Javascript判断浏览器终端设备
- jxl读取excel实现导入excel写入数据库
- [译]ES6箭头函数和它的作用域
- 清除div中内容
- vsftpd.conf Details
- C#中的多线程 - 基础知识
- 转 python range 用法
- android优化从网络中加载图片速度。。
- rsyslog
- 【Oracle 函数索引】一次数据库的优化过程
- android 自定义ViewGroup和对view进行切图动画实现滑动菜单SlidingMenu
- 一、Bitmap的recycle问题
- PIL PNG格式通道问题的解决方法
- 手工编程:hello world
- mysql学习------MySQL慢查询日志
- R语言日期的表示和运算(详细总结)
- Centos7安装最新版本的docker
- [JLOI2014]松鼠的新家(线段树,树链剖分)