办公门户网站模板下载,平面设计招聘58同城,wordpress网站视频播放,昆明做网站找哪个公司好文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
让我们一起来玩扫雷游戏#xff01;
给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷#xff0c; ‘E’ 代表一个未挖出的空方块#xff0c; ‘B’ 代表没有相邻#xff08;上#xff0c;下#xff0c;左…
文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
让我们一起来玩扫雷游戏
给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷 ‘E’ 代表一个未挖出的空方块 ‘B’ 代表没有相邻上下左右和所有4个对角线地雷的已挖出的空白方块 数字‘1’ 到 ‘8’表示有多少地雷与这块已挖出的方块相邻 ‘X’ 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中‘M’或者’E’的下一个点击位置行和列索引 根据以下规则返回相应位置被点击后对应的面板
如果一个地雷‘M’被挖出游戏就结束了- 把它改为 ‘X’。如果一个没有相邻地雷的空方块‘E’被挖出修改它为‘B’并且所有和其相邻的方块都应该被递归地揭露。如果一个至少与一个地雷相邻的空方块‘E’被挖出修改它为数字‘1’到’8’表示相邻地雷的数量。如果在此次点击中若无更多方块可被揭露则返回面板。
示例 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)这也意味着面板至少包含一个可点击的方块。
输入面板不会是游戏结束的状态即有地雷已被挖出。
简单起见未提及的规则在这个问题中可被忽略。
例如当游戏结束时你不需要挖出所有地雷考虑所有你可能赢得游戏或标记方块的情况。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minesweeper 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 BFS
class Solution {
public:vectorvectorchar updateBoard(vectorvectorchar board, vectorint click) {if(board[click[0]][click[1]] M)//点击的是地雷直接标记X结束{board[click[0]][click[1]] X;return board;}vectorvectorint 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;queuevectorint q;q.push(click);vectorvectorbool visited(m,vectorbool(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(x0 xm y0 yn board[x][y]M)count;//8个方向有几颗地雷}if(count 0)//地雷为0需要周围的都加入队列去检查是否继续翻开{board[i][j] B;//中间标记为Bfor(k 0; k 8; k){x i dir[k][0];y j dir[k][1];if(x0 xm y0 yn !visited[x][y] board[x][y]E){q.push({x,y});visited[x][y] true;}}}else{ //不为零标记为数字board[i][j] char(0count);}}return board;}
};2.2 DFS
class Solution {vectorvectorint dir {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};int m,n;
public:vectorvectorchar updateBoard(vectorvectorchar board, vectorint click) {if(board[click[0]][click[1]] M){board[click[0]][click[1]] X;return board;}m board.size(), n board[0].size();vectorvectorbool visited(m,vectorbool(n,false));visited[click[0]][click[1]] true;dfs(board,click[0],click[1],visited);return board;}void dfs(vectorvectorchar board, int i, int j, vectorvectorbool visited){int x, y, k, count 0;for(k 0; k 8; k){x i dir[k][0];y j dir[k][1];if(x0 xm y0 yn board[x][y]M)count;//8个方向有几颗地雷}if(count 0)//地雷为0需要周围的都加入队列去检查是否继续翻开{board[i][j] B;//中间标记为Bfor(k 0; k 8; k){x i dir[k][0];y j dir[k][1];if(x0 xm y0 yn !visited[x][y] board[x][y]E){visited[x][y] true;dfs(board,x,y,visited);}}}else{ //不为零标记为数字board[i][j] char(0count);}}
};
