LeetCode[BFS]: 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

参考：https://oj.leetcode.com/discuss/9942/my-bfs-solution-c-28ms

采取逆向思维，不是找到所有被’X’包围的’O’，而是将所有未被包围的’O’先标记为’#’，然后将剩余的’O’标记为’X’，将’#’标记为’O’，即可达到想要的目的。

C++代码实现如下：

class Solution {public:void solve(vector<vector<char>> &board) {int height = board.size();if (height == 0) return;int width = board[0].size();if (width == 0) return;for (int i = 0; i < height; ++i) {if (board[i][0] == ‘O’) BFSBoundary(board, i, 0);if (board[i][width – 1] == ‘O’) BFSBoundary(board, i, width – 1);}for (int j = 1; j < width – 1; ++j) {if (board[0][j] == ‘O’) BFSBoundary(board, 0, j);if (board[height – 1][j] == ‘O’) BFSBoundary(board, height – 1, j);}for (int i = 0; i < height; ++i) {for (int j = 0; j < width; ++j) {if (board[i][j] == ‘O’) board[i][j] = ‘X’;if (board[i][j] == ‘#’) board[i][j] = ‘O’;}}}private:void BFSBoundary(vector<vector<char>> &board, int h, int w) {int height = board.size();int width = board[0].size();queue<pair<int, int>> q;q.push(make_pair(h, w));board[h][w] = ‘#’;while (!q.empty()) {pair<int, int> point = q.front();q.pop();pair<int, int> neighbors[4] = { { point.first + 1, point.second },{ point.first – 1, point.second },{ point.first, point.second + 1 },{ point.first, point.second – 1 } };for (auto neig : neighbors) {if ((neig.first >= 0 && neig.first < height)&& (neig.second >= 0 && neig.second < width)&& (board[neig.first][neig.second] == ‘O’)){q.push(make_pair(neig.first, neig.second));board[neig.first][neig.second] = ‘#’;}}}}};

，你所缺少的部分，也早已被我用想像的画笔填满。