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就行了。代码如下：
解法一：
class Solution { public: void solve(vector<vector<char> >& board) { for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { if ((i == 0 || i == board.size() - 1 || j == 0 || j == board[i].size() - 1) && board[i][j] == 'O') solveDFS(board, i, j); } } for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { if (board[i][j] == 'O') board[i][j] = 'X'; if (board[i][j] == '$') board[i][j] = 'O'; } } } void solveDFS(vector<vector<char> > &board, int i, int j) { if (board[i][j] == 'O') { board[i][j] = '$'; if (i > 0 && board[i - 1][j] == 'O') solveDFS(board, i - 1, j); if (j < board[i].size() - 1 && board[i][j + 1] == 'O') solveDFS(board, i, j + 1); if (i < board.size() - 1 && board[i + 1][j] == 'O') solveDFS(board, i + 1, j); if (j > 1 && board[i][j - 1] == 'O') solveDFS(board, i, j - 1); } } };
有网友提问上面的代码中红色部分为啥是j > 1 而不是j > 0，为啥j > 0无法通过OJ的最后一个大数据集合，我开始也不知道其中奥秘，直到被另一个网友提醒在本地机子上可以通过最后一个大数据集合，于是我也写了一个程序来验证，请参见验证LeetCode Surrounded Regions 包围区域的DFS方法。发现j > 0是正确的，可以得到相同的结果。
解法二：
class Solution { public: void solve(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); } } } };
本文转自博客园Grandyang的博客，原文链接：包围区域[LeetCode] Surrounded Regions ，如需转载请自行联系原博主。