首页 > 代码库 > Surrounded Regions

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 XX O O XX X O XX O X X

 

After running your function, the board should be:

X X X XX X X XX X X XX O X X
class Solution {public:    void bfsBoundary(vector<vector<char> >& board, int w, int l)    {        int width = board.size();        int length = board[0].size();        deque<pair<int, int> > q;        q.push_back(make_pair(w, l));        board[w][l] = B;        while (!q.empty()) {            pair<int, int> cur = q.front();            q.pop_front();            pair<int, int> adjs[4] = {{cur.first-1, cur.second},                 {cur.first+1, cur.second},                 {cur.first, cur.second-1},                {cur.first, cur.second+1}};            for (int i = 0; i < 4; ++i)            {                int adjW = adjs[i].first;                int adjL = adjs[i].second;                if ((adjW >= 0) && (adjW < width) && (adjL >= 0)                        && (adjL < length)                         && (board[adjW][adjL] == O)) {                    q.push_back(make_pair(adjW, adjL));                    board[adjW][adjL] = B;                }            }        }    }        void solve(vector<vector<char> > &board) {        int width = board.size();        if (width == 0)             return;        int length = board[0].size();        if  (length == 0)             return;            for (int i = 0; i < length; ++i)        {            if (board[0][i] == O)                bfsBoundary(board, 0, i);                if (board[width-1][i] == O)                bfsBoundary(board, width-1, i);        }            for (int i = 0; i < width; ++i)        {            if (board[i][0] == O)                bfsBoundary(board, i, 0);            if (board[i][length-1] == O)                bfsBoundary(board, i, length-1);        }            for (int i = 0; i < width; ++i)        {            for (int j = 0; j < length; ++j)            {                if (board[i][j] == O)                    board[i][j] = X;                else if (board[i][j] == B)                    board[i][j] = O;            }        }    }};

 

Surrounded Regions