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); } };
本文转自博客园Grandyang的博客，原文链接：包围区域[LintCode] Surrounded Regions ，如需转载请自行联系原博主。