LeetCode: 529. Minesweeper

2019-11-06 09:02:26

字体：大中小

来源：转载

供稿：网友

LeetCode: 529. Minesweeper

题目基本是写一个简要版的Minesweeper，给出了三个规则：

如果点到一个隐藏的地雷M，把它改为X，游戏结束如果点到一个E，且其周围8邻接的范围没有地雷，那么应该把8邻接的范围的格子全部翻开为E如果翻开的格子的八邻接范围有隐藏的地雷，就将其标注了地雷的数目1-8而非E

一开始感觉题目还是有没说清楚的地方，就是原题里只提到邻接范围，而没有仔细说明是4邻接还是8邻接。后来仔细想想，扫雷都是指一个九宫格里的地雷数（比较少玩，所以一开始没想起来……），所以是8邻域。至于解法，其实题目条件2已经暴露了–recursively，递归搜索，就是BFS或者DFS了。其中BFS比较好理解（参考二叉树的层次遍历）。

BFS

用deque是因为可以实现双向插入删除，其实就BFS而言，是一个先进先出的队列，用list也是没有问题的。

时间复杂度是O(n*m)，空间复杂度是O(n*m)。

vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click){ int column = click[0]; int row = click[1]; deque<pair<int,int>> EToBeRevealed; EToBeRevealed.clear(); //1. if(board[column][row] == 'M') board[column][row] = 'X'; else if(board[column][row] == 'E') { EToBeRevealed.push_back({column,row}); while(!EToBeRevealed.empty()) { pair<int,int> reveal = EToBeRevealed.front(); int tc = reveal.first; int tr = reveal.second; EToBeRevealed.pop_front(); if(board[tc][tr] == 'B') continue; board[tc][tr] = 'B'; //number of 'M' around int numOfUnrevealedM = 0; vector<pair<int,int>> toBePush; for(int pc = -1;pc <= 1;pc++) { for(int PR = -1;pr <= 1;pr++) { if(tc+pc >= 0&& tc+pc < board.size() && tr+pr >= 0 && tr+pr < board[0].size()) { if(board[tc+pc][tr+pr] == 'E') toBePush.push_back({tc+pc,tr+pr}); if(board[tc+pc][tr+pr] == 'M') { numOfUnrevealedM++; } } } } //3. if(numOfUnrevealedM) board[tc][tr] = '0' + numOfUnrevealedM; //find 'E' around else EToBeRevealed.insert(EToBeRevealed.end(),toBePush.begin(),toBePush.end()); } } return board;}

要注意要剔除visited的格子，一个格子能被加入EToBeRevealed中很多次，但是通过检查是否visited（是否为B）保证只执行一次，不然队列会变得非常大，超出时间的限制。

各种循环的判定和操作都要小心。vector的初始化可以用｛,,,｝。

还有DFS版本的，用的递归。个人不是很推荐，容易出错，虽然代码会简洁些。

DFS

vector<pair<int,int>> link = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};vector<char> mines = {'B', '1','2','3','4','5','6','7','8'};vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) { int m = board.size(); int n = board[0].size(); if(board[click[0]][click[1]] == 'M') {board[click[0]][click[1]] = 'X'; return board;} dfs(board, click[0], click[1], m, n); return board;}void dfs(vector<vector<char>>& board, int i, int j, int m, int n){ if(i < 0 || i >= m || j < 0 || j >= n) return; if(board[i][j] == 'E'){ int count = 0; for(auto d : link){ int tmpi = i + d.first; int tmpj = j + d.second; if(tmpi >= 0 && tmpi < m && tmpj >= 0 && tmpj < n){ if(board[tmpi][tmpj] == 'M') count++; } } board[i][j] = mines[count]; if(board[i][j] == 'B'){ for(auto lk : link){ dfs(board, i+lk.first, j+lk.second, m, n); } } }}

上一篇：keil4 破解心得

下一篇：曼哈顿距离