软件定制开发网站,局域网的电脑怎么做网站服务器,济南专业网站建设咨询,东坑镇网站建设目录 一#xff0c;题目
二#xff0c;题目接口
三#xff0c;解题思路
四#xff0c;解题代码 一#xff0c;题目 让我们一起来玩扫雷游戏#xff01; 给你一个大小为 m x n 二维字符矩阵 board #xff0c;表示扫雷游戏的盘面#xff0c;其中#xff1a; M 代表一…
目录 一题目
二题目接口
三解题思路
四解题代码 一题目 让我们一起来玩扫雷游戏 给你一个大小为 m x n 二维字符矩阵 board 表示扫雷游戏的盘面其中 M 代表一个 未挖出的 地雷E 代表一个 未挖出的 空方块B 代表没有相邻上下左右和所有4个对角线地雷的 已挖出的 空白方块数字1 到 8表示有多少地雷与这块 已挖出的 方块相邻X 则表示一个 已挖出的 地雷。 给你一个整数数组 click 其中 click [clickr, clickc] 表示在所有 未挖出的 方块M 或者 E中的下一个点击位置clickr 是行下标clickc 是列下标。 根据以下规则返回相应位置被点击后对应的盘面 如果一个地雷M被挖出游戏就结束了- 把它改为 X 。如果一个 没有相邻地雷 的空方块E被挖出修改它为B并且所有和其相邻的 未挖出 方块都应该被递归地揭露。如果一个 至少与一个地雷相邻 的空方块E被挖出修改它为数字1 到 8 表示相邻地雷的数量。如果在此次点击中若无更多方块可被揭露则返回盘面。 二题目接口
class Solution {
public:vectorvectorchar updateBoard(vectorvectorchar board, vectorint click) {}
};
三解题思路 对于这道题采取的解法是模拟dfs。首先讲一下模拟扫雷游戏该如何模拟呢分下列两种情况 1.第一次点击的时候正好点击到了雷这个时候就直接将这个位置的字母M改为X然后返回棋盘便可以了。 2.如果第一次点击没有点击到雷那我们就可以进入到下一阶段的模拟。这个阶段的模拟首先得检查在这个位置的周围是否有雷如果有便将这个位置的值改为雷的个数。如果这个位置周围没有雷那就将这个位置的值改为字符B然后递归这个位置周围的八个位置。 四解题代码
class Solution {
public:int m,n;int dx[8] {0,0,1,-1,1,1,-1,-1},dy[8] {1,-1,0,0,1,-1,1,-1};//向量表示八个位置对应的下标vectorvectorchar updateBoard(vectorvectorchar board, vectorint click) {int x click[0];int y click[1];m board.size();n board[0].size();if(board[x][y] M){board[x][y] X;return board;}dfs(x,y,board);return board;}void dfs(int i,int j,vectorvectorcharboard){int count 0;for(int k 0;k8;k)//搜索周围的八个位置查看是否有雷。{int x idx[k],y jdy[k];if(x0xmy0ynboard[x][y] M){count;}}if(count)//若有便将该位置上的值改为雷的个数{board[i][j] 0count;}else{for(int k 0;k8;k)//若无便搜索该位置周围的八个位置。{board[i][j] B;int x idx[k],y jdy[k];if(x0xmy0ynboard[x][y] E){dfs(x,y,board);}}}}
};
