首页 > 代码库 > Surrounded Regions
Surrounded Regions
Given a 2D board containing ‘X‘
and ‘O‘
, capture all regions surrounded by ‘X‘
.
A region is captured by flipping all ‘O‘
s into ‘X‘
s in that surrounded region.
For example,
X X X XX O O XX X O XX O X X
After running your function, the board should be:
X X X XX X X XX X X XX O X X
class Solution {public: void bfsBoundary(vector<vector<char> >& board, int w, int l) { int width = board.size(); int length = board[0].size(); deque<pair<int, int> > q; q.push_back(make_pair(w, l)); board[w][l] = ‘B‘; while (!q.empty()) { pair<int, int> cur = q.front(); q.pop_front(); pair<int, int> adjs[4] = {{cur.first-1, cur.second}, {cur.first+1, cur.second}, {cur.first, cur.second-1}, {cur.first, cur.second+1}}; for (int i = 0; i < 4; ++i) { int adjW = adjs[i].first; int adjL = adjs[i].second; if ((adjW >= 0) && (adjW < width) && (adjL >= 0) && (adjL < length) && (board[adjW][adjL] == ‘O‘)) { q.push_back(make_pair(adjW, adjL)); board[adjW][adjL] = ‘B‘; } } } } void solve(vector<vector<char> > &board) { int width = board.size(); if (width == 0) return; int length = board[0].size(); if (length == 0) return; for (int i = 0; i < length; ++i) { if (board[0][i] == ‘O‘) bfsBoundary(board, 0, i); if (board[width-1][i] == ‘O‘) bfsBoundary(board, width-1, i); } for (int i = 0; i < width; ++i) { if (board[i][0] == ‘O‘) bfsBoundary(board, i, 0); if (board[i][length-1] == ‘O‘) bfsBoundary(board, i, length-1); } for (int i = 0; i < width; ++i) { for (int j = 0; j < length; ++j) { if (board[i][j] == ‘O‘) board[i][j] = ‘X‘; else if (board[i][j] == ‘B‘) board[i][j] = ‘O‘; } } }};
Surrounded Regions
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。