首页 > 代码库 > Surrounded Regions
Surrounded Regions
130. Surrounded Regions
题目链接:https://leetcode.com/problems/surrounded-regions/#/description
题目大意:给定一个二维的板,板上是‘X‘或‘O‘字符,捕获所有被‘X‘包围的区域,在该区域内的字符‘O‘翻转为‘X‘。
思路:从板的边界出发,获取边界的所有‘O‘字符的坐标,然后从这些坐标出发,宽度优先搜素所有与边界的‘O‘联通的‘O‘,所有搜索过的‘O‘都修改为字符‘1‘,则宽度优先搜索结束后,所有字符为‘1‘的表示未被字符‘X‘包围的‘O‘,字符为‘O‘的为被‘X‘包围的‘O‘。
代码:
1 class Solution { 2 public: 3 void solve(vector<vector<char>>& board) { 4 if (board.empty() || board[0].empty()) 5 return; 6 vector<pair<int, int>> oCoordates; 7 int row = board.size(), col = board[0].size(); 8 for (int i = 0; i < 2; ++i) { 9 int x = i ? 0 : row - 1; 10 for (int j = 0; j < col; ++j) 11 if (board[x][j] == ‘O‘) { 12 oCoordates.push_back(make_pair(x, j)); 13 board[x][j] = ‘1‘; 14 } 15 } 16 for (int i = 0; i < 2; ++i) { 17 int y = i ? 0 : col - 1; 18 for (int j = 0; j < row; ++j) 19 if (board[j][y] == ‘O‘) { 20 oCoordates.push_back(make_pair(j, y)); 21 board[j][y] = ‘1‘; 22 } 23 } 24 while (!oCoordates.empty()) { 25 auto coordates = oCoordates.back(); 26 oCoordates.pop_back(); 27 for (int i = -1; i < 2; i += 2) { 28 findOCoordates(board, oCoordates, coordates.first, coordates.second + i); 29 findOCoordates(board, oCoordates, coordates.first + i, coordates.second); 30 } 31 32 } 33 for (int i = 0; i < board.size(); ++i) 34 for (int j = 0; j < board[0].size(); ++j) 35 if (board[i][j] == ‘1‘) 36 board[i][j] = ‘O‘; 37 else if (board[i][j] == ‘O‘) 38 board[i][j] = ‘X‘; 39 } 40 private: 41 void findOCoordates(vector<vector<char>>& board, vector<pair<int, int>> &oCoordates, int x, int y) { 42 if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] == ‘O‘) { 43 oCoordates.push_back(make_pair(x, y)); 44 board[x][y] = ‘1‘; 45 } 46 } 47 };
评测系统上运行结果:
Surrounded Regions
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。