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 X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
核心思想：只有边界上'O'的位置组成的片区不会被'X'包围。
因此先对边界上的'O'遍历之后暂存为'*'。
非'*'的'O'即被'X'包围了。
解法一：DFS遍历
struct POS
{
int x;
int y;
POS(int newx, int newy): x(newx), y(newy) {}
}; class Solution {
public:
void solve(vector<vector<char>> &board) {
if(board.empty() || board[].empty())
return;
int m = board.size();
int n = board[].size();
for(int i = ; i < m; i ++)
{
for(int j = ; j < n; j ++)
{
if(board[i][j] == 'O')
{
if(i == || i == m- || j == || j == n-)
{// remain 'O' on the boundry
dfs(board, i, j, m, n);
}
}
}
}
for(int i = ; i < m; i ++)
{
for(int j = ; j < n; j ++)
{
if(board[i][j] == 'O')
board[i][j] = 'X';
else if(board[i][j] == '*')
board[i][j] = 'O';
}
}
}
void dfs(vector<vector<char>> &board, int i, int j, int m, int n)
{
stack<POS*> stk;
POS* pos = new POS(i, j);
stk.push(pos);
board[i][j] = '*';
while(!stk.empty())
{
POS* top = stk.top();
if(top->x > && board[top->x-][top->y] == 'O')
{
POS* up = new POS(top->x-, top->y);
stk.push(up);
board[up->x][up->y] = '*';
continue;
}
if(top->x < m- && board[top->x+][top->y] == 'O')
{
POS* down = new POS(top->x+, top->y);
stk.push(down);
board[down->x][down->y] = '*';
continue;
}
if(top->y > && board[top->x][top->y-] == 'O')
{
POS* left = new POS(top->x, top->y-);
stk.push(left);
board[left->x][left->y] = '*';
continue;
}
if(top->y < n- && board[top->x][top->y+] == 'O')
{
POS* right = new POS(top->x, top->y+);
stk.push(right);
board[right->x][right->y] = '*';
continue;
}
stk.pop();
}
}
};
解法二：BFS遍历
struct POS
{
int x;
int y;
POS(int newx, int newy): x(newx), y(newy) {}
}; class Solution {
public:
void solve(vector<vector<char>> &board) {
if(board.empty() || board[].empty())
return;
int m = board.size();
int n = board[].size();
for(int i = ; i < m; i ++)
{
for(int j = ; j < n; j ++)
{
if(board[i][j] == 'O')
{
if(i == || i == m- || j == || j == n-)
{// remain 'O' on the boundry
bfs(board, i, j, m, n);
}
}
}
}
for(int i = ; i < m; i ++)
{
for(int j = ; j < n; j ++)
{
if(board[i][j] == 'O')
board[i][j] = 'X';
else if(board[i][j] == '*')
board[i][j] = 'O';
}
}
}
void bfs(vector<vector<char>> &board, int i, int j, int m, int n)
{
queue<POS*> q;
board[i][j] = '*';
POS* pos = new POS(i, j);
q.push(pos);
while(!q.empty())
{
POS* front = q.front();
q.pop();
if(front->x > && board[front->x-][front->y] == 'O')
{
POS* up = new POS(front->x-, front->y);
q.push(up);
board[up->x][up->y] = '*';
}
if(front->x < m- && board[front->x+][front->y] == 'O')
{
POS* down = new POS(front->x+, front->y);
q.push(down);
board[down->x][down->y] = '*';
}
if(front->y > && board[front->x][front->y-] == 'O')
{
POS* left = new POS(front->x, front->y-);
q.push(left);
board[left->x][left->y] = '*';
}
if(front->y < n- && board[front->x][front->y+] == 'O')
{
POS* right = new POS(front->x, front->y+);
q.push(right);
board[right->x][right->y] = '*';
}
}
}
};
这边再给一种递归实现的dfs供参考，简洁很多，但是在leetcode中由于栈溢出会显示Runtime Error
void dfs(vector<vector<char>> &board, int i, int j, int m, int n)
{
board[i][j] = '*';
if(i > && board[i-][j] == 'O') // up
dfs(board, i-, j, m, n);
if(i < m- && board[i+][j] == 'O') // down
dfs(board, i+, j, m, n);
if(j > && board[i][j-] == 'O') // left
dfs(board, i, j-, m, n);
if(j < n- && board[i][j+] == 'O') // right
dfs(board, i, j+, m, n);
}