leetcode529. Minesweeper
2020/1/30 5:00:20
本文主要是介绍leetcode529. Minesweeper,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目要求
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.
玩过扫雷游戏的同学应该熟悉扫雷的规则,这题的目标在于模拟扫雷游戏,它给了一块已经完成一部分操作的扫雷面板,并且输入了下一步点击的位置。要求输出执行这次点击后面板的最新状态。
其中M表示隐藏的雷,X表示被点开的雷。E表示未被点开的空格,B表示被点开的空格,数字1到8表示距离该格子一圈一共有几个雷。
当玩家点击了格子后,一共有三种情况
- 点中了M,则将该格子更新为X,游戏结束
- 点中了B,且周围有雷,则记录该格子周围一共几个雷,并将数量标记到这个格子上
- 点中了B,且周围无雷,则继续向周围一圈排雷。
思路和代码
这是一道典型的通过广搜或是深搜解决的题目。广搜即以雷区为中心,每次向外搜索一圈,深搜则是搜索到全是雷区为止。广搜代码如下:
public char[][] updateBoard(char[][] board, int[] click) { char clickValue = board[click[0]][click[1]]; if (clickValue == 'M') { board[click[0]][click[1]] = 'X'; } else if (clickValue == 'E') { //广度优先遍历 Queue<int[]> queue = new LinkedList<>(); queue.offer(click); //8个方向 int[][] directions = new int[][]{ {0, 1}, {0, -1}, {-1, 0}, {1, 0}, {-1, -1}, {-1, 1}, {1, 1}, {1,-1} }; while (!queue.isEmpty()) { int[] tmpClick = queue.poll(); int countOfMine = 0; List<int[]> emptyCells = new ArrayList<>(); for (int\[] direction : directions) { int rowIndex = direction[0] + tmpClick[0]; int columnIndex = direction[1] + tmpClick[1]; if (rowIndex < 0 || rowIndex >= board.length || columnIndex < 0 || columnIndex >= board[0].length) { continue; } if (board[rowIndex][columnIndex] == 'M') { countOfMine++; } else if (board[rowIndex][columnIndex] == 'E') { emptyCells.add(new int[]{rowIndex, columnIndex}); } } if (countOfMine == 0) { board[tmpClick[0]][tmpClick[1]] = 'B'; //防止重复遍历,先将其置为B for (int[] emptyCell : emptyCells) { board[emptyCell[0]][emptyCell[1]] = 'B'; } queue.addAll(emptyCells); } else { board[tmpClick[0]][tmpClick[1]] = (char)('0' + countOfMine); } } } return board; }
深搜代码如下:
public char[][] updateBoard2(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; }
这篇关于leetcode529. Minesweeper的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望