Start learning free

LESSON 500 OF 568 · GRAPHS

Surrounded Regions in C++: BFS from the Edge in O(m * n)

Practice O(m · n) Read the full explanation

You are given board, a grid of m rows and n columns in which every cell holds the letter 'X' or the letter 'O'. It is a vector of rows, and each row is a vector of single letters.

Two 'O' cells are connected when one is directly above, below, left or right of the other (not diagonally). A region is a group of 'O' cells that can all be reached from each other through connected cells, and that no other 'O' is connected to.

A region is surrounded when none of its cells lies on the edge of the board (the first or the last row, the first or the last column): 'X' cells close it in on every side. Capture every surrounded region by changing all of its cells to 'X'. A region with at least one cell on the edge is not captured and stays as it is.

Change board in place and return nothing: the board you were given must hold the result.

 

Example 1:

Input: board =
X X X X
X O O X
X X O X
X O X X

Output:
X X X X
X X X X
X X X X
X O X X

Explanation: The three red cells form one region, and none of them is on the edge, so it is
captured. The green 'O' is in the last row, on the edge: it is not captured.

Example 2:

Input: board =
O

Output:
O

Explanation: The only cell is on every edge of the board, so it is not captured.

Example 3:

Input: board =
O X X X X
X O O O X
X X X O X
X O X O X
X X X O X

Output:
O X X X X
X O O O X
X X X O X
X X X O X
X X X O X

Explanation: The green region in the middle winds down to the 'O' in the last row, which is on
the edge, so none of it is captured. The 'O' in the top-left corner touches that region only diagonally,
which doesn't connect them, but it is on the edge itself. The red 'O' is closed in by 'X' on all four
sides: it is captured.

 

Constraints:

  • 1 <= m, n <= 200
  • Every row has n cells.
  • Every cell is 'X' or 'O'.

Note:

Your algorithm should run in O(m · n) time and use O(m · n) extra space.

Checking every 'O' on its own, with a search that looks for a way to the edge, can cost O((m · n)2): think of one large region in the middle of the board that is searched again from each of its cells. The tutorial turns the question around, as Pacific Atlantic Water Flow does, and starts from the edge. Every 'O' on the edge is safe, and so is every 'O' connected to a safe one. A BFS that starts from all the 'O's on the edge at once marks every safe cell, and each cell joins its queue at most once. Then one pass over the board turns every 'O' that is not marked into 'X'.

Use a queue, or a stack of your own, rather than recursion: one region can wind through the whole board, and a recursive search tens of thousands of calls deep runs out of call stack in some languages.

STEP 1 OF 21
    Ctrl + Enter to check

    C++ · GRAPHS

    Surrounded Regions in C++, explained

    Problem overview

    The method solve receives board, a vector<vector<char>> of m rows and n columns where every cell is 'X' or 'O'. Two 'O' cells are connected when one is directly above, below, left or right of the other; diagonals don't count. A region is a maximal group of connected 'O' cells. A region is surrounded when none of its cells lies on the edge of the board, and every surrounded region must be captured: all its cells become 'X'. A region with a cell on the edge stays as it is.

    The method returns nothing. It changes board in place.

    In the first example the board is

    XXXX
XOOX
XXOX
XOXX

    The three 'O' cells in the middle form one region and none of them is on the edge, so they become 'X'. The 'O' in the last row is on the edge and stays:

    XXXX
XXXX
XXXX
XOXX

    A board with a single 'O' is unchanged, because that one cell is on every edge.

    Approach: mark what is safe, starting from the edge

    The direct way is to take each 'O' and search for a path of 'O' cells to the edge. A big region in the middle of the board would then be searched again from each of its cells, which can cost O((m * n)^2).

    Turning the question around avoids that. Every 'O' on the edge is safe, and so is every 'O' connected to a safe one. So start from all the edge 'O' cells at once and spread inward with a breadth-first search, marking each cell it reaches. Every cell enters the queue at most once. After the search, every 'O' that is not marked has no path of 'O' cells to the edge, so its region is surrounded, and one pass over the board turns those cells into 'X'.

    The search uses a queue instead of recursion. One region can wind through the whole board, and a recursive search that goes tens of thousands of calls deep can exhaust the call stack. A 200 by 200 board has 40,000 cells.

    Third example, a board where the edge matters:

    OXXXX
XOOOX
XXXOX
XOXOX
XXXOX

    The middle region winds down to the last row, which is on the edge, so all of it is safe. The 'O' at the top left touches that region only diagonally, but it is on the edge itself. The 'O' at row 3, column 1 is closed in on all four sides and is the only cell that changes:

    OXXXX
XOOOX
XXXOX
XXXOX
XXXOX

    Step by step

    1. Store the dimensions. rows is board.size() and cols is board[0].size(). Every row has the same length, so the first row gives the number of columns.
    2. Create the safe grid. A vector<vector<bool>> of the same size as the board, all false. A cell is marked true when it holds an 'O' connected to the edge.
    3. Create the queue. queue<pair<int, int>> q holds the safe cells whose neighbours still have to be checked, as (row, column) pairs.
    4. Loop over the rows,
    5. and over the columns, to find the 'O' cells on the edge in a first pass over the board.
    6. Test for the edge. A cell is on the border when it is in the first or last row or the first or last column: four tests joined with ||.
    7. Select border 'O' cells. onBorder && board[r][c] == 'O' picks the starting points of the search.
    8. Mark the cell safe. Marking a cell when it joins the queue means no other cell can add it a second time.
    9. Push {r, c} onto the queue.
    10. Define the four moves. The directions vector holds up, down, left and right as (row change, column change) pairs. Each move changes only one coordinate, so diagonal cells are never neighbours.
    11. Loop while the queue is not empty. Each turn handles one safe cell.
    12. Take the front cell. auto [row, col] = q.front() unpacks the pair, and q.pop() removes it. pop() returns nothing, so the read comes first.
    13. Loop over the moves, unpacking each into dr and dc.
    14. Compute the neighbour: nextRow = row + dr and nextCol = col + dc.
    15. Check that it is on the board. It may lie outside, and it must not be used as an index before this test.
    16. Check that it is an unmarked 'O'. An 'O' next to a safe 'O' is in the same region, so it is connected to the edge. The !safe test keeps it from joining the queue twice.
    17. Mark it,
    18. and push {nextRow, nextCol}. Its own neighbours are checked when it leaves the queue.
    19. Loop over every cell again, rows first,
    20. then columns.
    21. Capture. An 'O' that is not marked safe becomes 'X'.

    The solution in C++

    class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int rows = board.size();
        int cols = board[0].size();
        vector<vector<bool>> safe(rows, vector<bool>(cols, false));
        queue<pair<int, int>> q;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                bool onBorder = r == 0 || r == rows - 1 || c == 0 || c == cols - 1;
                if (onBorder && board[r][c] == 'O') {
                    safe[r][c] = true;
                    q.push({r, c});
                }
            }
        }
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!q.empty()) {
            auto [row, col] = q.front();
            q.pop();
            for (auto [dr, dc] : directions) {
                int nextRow = row + dr;
                int nextCol = col + dc;
                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
                    if (board[nextRow][nextCol] == 'O' && !safe[nextRow][nextCol]) {
                        safe[nextRow][nextCol] = true;
                        q.push({nextRow, nextCol});
                    }
                }
            }
        }
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == 'O' && !safe[r][c]) {
                    board[r][c] = 'X';
                }
            }
        }
    }
};

    The C++ details worth a closer look:

    • In-place change through a reference. The parameter is vector<vector<char>>&, so board[r][c] = 'X' changes the caller's board and the method needs no return value.
    • The grid constructor. vector<vector<bool>> safe(rows, vector<bool>(cols, false)) makes rows copies of a row of cols false values. vector<bool> is a special packed version of vector that stores one bit per element; for this use it behaves like any other vector.
    • Structured bindings. auto [row, col] = q.front() copies the pair out and names its two parts. It needs C++17. The copy matters: q.pop() would invalidate a reference to the front element, so the pair is taken by value before the pop.
    • q.push({r, c}). The braces build the pair<int, int> in place.
    • Checking bounds before indexing. Indexing a vector outside its range is undefined behaviour, so the bounds test comes first, and && and the nested if keep board[nextRow][nextCol] from being read for an off-board position.
    • Char literals. 'O' and 'X' are char values, the type of each cell. Double quotes would make a string, which can't be compared with a char.

    Complexity

    Time: O(m * n). The first pass visits each cell once. Each cell enters the queue at most once and looks at 4 neighbours when it leaves. The last pass visits each cell once.

    Space: O(m * n). The safe grid has one entry per cell, and the queue never holds more cells than the board has.

    Edge cases and common mistakes

    • Capturing every 'O' that isn't on the edge. That ignores the connection: a region that winds to the edge is safe. On the third example it returns OXXXX / XXXXX / XXXXX / XXXXX / XXXOX, the same wrong board as the next mistake.
    • Spreading diagonally. Using all 8 neighbours joins regions that the problem keeps apart. On the board XXXXX / OXXXX / XOXXX / XXXXX, the 'O' at row 2, column 1 is surrounded, and the solution turns it into 'X'. With 8 neighbours it stays, saved by the edge 'O' next to it diagonally.
    • Not spreading at all. Marking only the 'O' cells on the edge and capturing every other 'O' destroys the safe cells that are connected to them. On the third example it returns OXXXX / XXXXX / XXXXX / XXXXX / XXXOX, which has lost the whole winding region except its last cell.
    • Single cell and tiny boards. A 1 x 1 board is entirely edge, so "O" stays "O". Any board with at most two rows or two columns has no interior at all, so nothing is captured.
    • A board that is all 'O'. Every cell is connected to the edge, and nothing changes. A 200 by 200 board of 'O' keeps all 40,000.
    • A region inside a frame. For a board with an 'X' border and 'O' cells inside, all the 'O' cells are captured: the 200 by 200 board with that shape ends with no 'O'.
    • Marking too late. Marking a cell when it leaves the queue instead of when it joins lets the same cell be pushed several times by different neighbours.

    Testing

    • XXXX / XOOX / XXOX / XOXX gives XXXX / XXXX / XXXX / XOXX.
    • O stays O.
    • XXX / XOX / XXX gives XXX / XXX / XXX.
    • OOO / OXO / OOO is unchanged.
    • XOX / OXO / XOX is unchanged: every 'O' is on the edge.
    • XXXXX / XOOOX / XOXOX / XOOOX / XXXXX, a ring of 'O' cells inside the frame, ends as all 'X'.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free