让我们一起来玩扫雷游戏! 给定一个代表游戏板的二维字符矩阵。 现在给出在所有未挖出的方块中(‘M’或者’E’)的下一个点击位置(行和列索引), 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minesweeper1. 题目
‘M’ 代表一个未挖出的地雷,
‘E’ 代表一个未挖出的空方块,
‘B’ 代表没有相邻(上,下,左,右,和所有4个对角线)地雷的已挖出的空白方块,
数字(‘1’ 到 ‘8’)表示有多少地雷与这块已挖出的方块相邻,
‘X’ 则表示一个已挖出的地雷。
根据以下规则,返回相应位置被点击后对应的面板:
示例 1: 输入: [['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'M', 'E', 'E'], ['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'E', 'E', 'E']] Click : [3,0] 输出: [['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']] 解释:
示例 2: 输入: [['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']] Click : [1,2] 输出: [['B', '1', 'E', '1', 'B'], ['B', '1', 'X', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']] 解释:
注意: 输入矩阵的宽和高的范围为 [1,50]。 点击的位置只能是未被挖出的方块 ('M' 或者 'E'),这也意味着面板至少包含一个可点击的方块。 输入面板不会是游戏结束的状态(即有地雷已被挖出)。 简单起见,未提及的规则在这个问题中可被忽略。 例如,当游戏结束时你不需要挖出所有地雷,考虑所有你可能赢得游戏或标记方块的情况。
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。2. 解题
2.1 BFS
class Solution { public: vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) { if(board[click[0]][click[1]] == 'M')//点击的是地雷,直接标记X,结束 { board[click[0]][click[1]] = 'X'; return board; } vector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}}; int m = board.size(), n = board[0].size(); int i, j, x, y, k, count; queue<vector<int>> q; q.push(click); vector<vector<bool>> visited(m,vector<bool>(n,false));//访问标记 visited[click[0]][click[1]] = true; while(!q.empty()) { i = q.front()[0]; j = q.front()[1]; q.pop(); count = 0; for(k = 0; k < 8; ++k) { x = i + dir[k][0]; y = j + dir[k][1]; if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='M') count++;//8个方向有几颗地雷 } if(count == 0)//地雷为0,需要周围的都加入队列,去检查是否继续翻开 { board[i][j] = 'B';//中间标记为B for(k = 0; k < 8; ++k) { x = i + dir[k][0]; y = j + dir[k][1]; if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && board[x][y]=='E') { q.push({x,y}); visited[x][y] = true; } } } else { //不为零,标记为数字 board[i][j] = char('0'+count); } } return board; } };
2.2 DFS
class Solution { vector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}}; int m,n; 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; } m = board.size(), n = board[0].size(); vector<vector<bool>> visited(m,vector<bool>(n,false)); visited[click[0]][click[1]] = true; dfs(board,click[0],click[1],visited); return board; } void dfs(vector<vector<char>>& board, int i, int j, vector<vector<bool>>& visited) { int x, y, k, count = 0; for(k = 0; k < 8; ++k) { x = i + dir[k][0]; y = j + dir[k][1]; if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='M') count++;//8个方向有几颗地雷 } if(count == 0)//地雷为0,需要周围的都加入队列,去检查是否继续翻开 { board[i][j] = 'B';//中间标记为B for(k = 0; k < 8; ++k) { x = i + dir[k][0]; y = j + dir[k][1]; if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && board[x][y]=='E') { visited[x][y] = true; dfs(board,x,y,visited); } } } else { //不为零,标记为数字 board[i][j] = char('0'+count); } } };
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算