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不算被包围，跟之前那道Number of Islands 岛屿的数量很类似，都可以用DFS来解。刚开始我的思路是DFS遍历中间的O，如果没有到达边缘，都变成X，如果到达了边缘，将之前变成X的再变回来。但是这样做非常的不方便，在网上看到大家普遍的做法是扫面矩阵的四条边，如果有O，则用DFS遍历，将所有连着的O都变成另一个字符，比如，这样剩下的O都是被包围的，然后将这些O变成X，把，这样剩下的O都是被包围的，然后将这些O变成X，把变回O就行了。代码如下：
class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty() || board[].empty()) return;
int m = board.size(), n = board[].size();
for (int i = ; i < m; ++i) {
for (int j = ; j < n; ++j) {
if (i == || i == m - || j == || j == n - ) {
if (board[i][j] == 'O') dfs(board, i , j);
}
}
}
for (int i = ; i < m; ++i) {
for (int j = ; 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[].size();
vector<vector<int>> dir{{,-},{-,},{,},{,}};
board[x][y] = '$';
for (int i = ; i < dir.size(); ++i) {
int dx = x + dir[i][], dy = y + dir[i][];
if (dx >= && dx < m && dy > && dy < n && board[dx][dy] == 'O') {
dfs(board, dx, dy);
}
}
}
};