# [LintCode] 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.
Example
X X X X
X O O X
X X O X
X O X X
After capture all regions surrounded by 'X', the board should be:
X X X X
X X X X
X X X X
X O X X

LeetCode上的原题，请参见我之前的博客Surrounded Regions

class Solution {
public:
/**
* @param board a 2D board containing 'X' and 'O'
* @return void
*/
void surroundedRegions(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) return;
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
if (board[i][j] == 'O') dfs(board, i , j);
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == '$') board[i][j] = 'O'; } } } void dfs(vector<vector<char>> &board, int x, int y) { int m = board.size(), n = board[0].size(); vector<vector<int>> dir{{0,-1},{-1,0},{0,1},{1,0}}; board[x][y] = '$';
for (int i = 0; i < dir.size(); ++i) {
int dx = x + dir[i][0], dy = y + dir[i][1];
if (dx >= 0 && dx < m && dy >= 0 && dy < n && board[dx][dy] == 'O') {
dfs(board, dx, dy);
}
}
}
};

class Solution {
public:
/**
* @param board a 2D board containing 'X' and 'O'
* @return void
*/
void surroundedRegions(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) return;
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
if (board[i][j] == 'O') dfs(board, i , j);
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == '$') board[i][j] = 'O'; } } } void dfs(vector<vector<char>> &board, int i, int j) { int m = board.size(), n = board[0].size(); if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return; board[i][j] = '$';
dfs(board, i + 1, j);
dfs(board, i - 1, j);
dfs(board, i, j + 1);
dfs(board, i, j - 1);
}
};

|
1月前
leetcode-1034：边界着色
leetcode-1034：边界着色
20 1
|
6月前
G2Plot Line 线性 x 轴头尾两头不留空白（或指定留白范围）
G2Plot Line 线性 x 轴头尾两头不留空白（或指定留白范围）
45 0
|
7月前
|

97 0
leetcode 435无重叠区
leetcode 435无重叠区
45 0
AcWing 749. 数组的上方区域
AcWing 749. 数组的上方区域
38 0
AcWing 750. 数组的下方区域
AcWing 750. 数组的下方区域
31 0
|

198 0
[路飞]_leetcode-130-被围绕的区域
leetcode-130-被围绕的区域
72 0
Halcon区域region的遍历，合并，旋转与排序
Halcon区域region的遍历，合并，旋转与排序
1312 0