Start learning free

LESSON 504 OF 572 · GRAPHS

Surrounded Regions in C#: Breadth-First Search from the Edge, 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 an array of rows, and each row is an array 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 char[][]: an array of rows, each row an array of 'X' and 'O' characters. Two 'O' cells are connected when one is directly above, below, left or right of the other. Diagonal cells are not connected. A region is a group of connected 'O' cells. A region is surrounded when none of its cells is on the edge of the board (first or last row, first or last column). The method must change every surrounded region to 'X', in place, and return nothing. A region with a cell on the edge stays as it is.

    In this board:

    X X X X
X O O X
X X O X
X O X X

    the three 'O' cells in the middle form a region that touches no edge, so they are captured. The 'O' in the last row is on the edge, so it stays:

    X X X X
X X X X
X X X X
X O X X

    Approach: start from the edge, not from the inside

    The direct way is to take each 'O' and search for a path of 'O' cells to the edge. That can repeat a lot of work: one big region in the middle gets searched again from each of its cells, which can cost O((m * n)^2).

    Turning the question around fixes this. An 'O' on the edge is never captured, and neither is any 'O' connected to one that is safe. So start from every 'O' on the edge at once, and spread inward through neighbouring 'O' cells, marking each one as safe. When the spreading ends, every 'O' that is not marked has no path to the edge, so its region is surrounded. One more pass over the board changes those cells to 'X'.

    The spreading is a breadth-first search (BFS) with a queue. A queue also keeps the search free of recursion, so a region that winds through the whole board can't exhaust the call stack.

    A tempting shortcut is to capture each 'O' whose four neighbours are all 'X'. That fails: on the board above it captures nothing, because each 'O' of the region has another 'O' as a neighbour. Connected cells must be treated as one region.

    Step by step

    1. Read the size. rows is board.Length, and cols is board[0].Length, since every row has the same length.
    2. Create the marks. bool[,] safe = new bool[rows, cols] is a rectangular array that starts all false. A cell becomes true when it is an 'O' connected to the edge.
    3. Create the queue of (int, int) tuples, the (row, column) cells whose neighbours are still to be checked.
    4. Find the edge cells. Two nested loops go over every cell. onBorder is true for the first or last row and the first or last column. When a cell is on the border and holds 'O', mark it in safe and enqueue it.
    5. List the four moves as tuples: (-1, 0), (1, 0), (0, -1) and (0, 1). Each changes the row or the column, never both, so diagonal neighbours are not reached.
    6. Run the BFS. While the queue isn't empty, dequeue a cell and unpack it into row and col.
    7. Visit the neighbours. For each move compute nextRow and nextCol. If the position is inside the board, and the cell holds 'O' and isn't marked yet, mark it and enqueue it. Marking when a cell joins the queue means no cell is enqueued twice.
    8. Capture. Go over the board once more. Every cell that holds 'O' and isn't marked safe becomes 'X'.

    The solution in C#

    class Solution {
    public void Solve(char[][] board) {
        int rows = board.Length;
        int cols = board[0].Length;
        bool[,] safe = new bool[rows, cols];
        Queue<(int, int)> queue = new Queue<(int, int)>();
        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;
                    queue.Enqueue((r, c));
                }
            }
        }
        (int, int)[] directions = { (-1, 0), (1, 0), (0, -1), (0, 1) };
        while (queue.Count > 0) {
            (int row, int col) = queue.Dequeue();
            foreach ((int dr, int dc) in 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;
                        queue.Enqueue((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 knowing:

    • Jagged and rectangular arrays together. char[][] is a jagged array, an array of arrays, indexed board[r][c]. bool[,] is a rectangular array, indexed safe[r, c] and created with new bool[rows, cols]. The two index syntaxes are easy to mix up, and the compiler rejects the wrong one.
    • Tuples. (int, int) is a value tuple type: two values kept together. queue.Enqueue((r, c)) builds one, and (int row, int col) = queue.Dequeue(); deconstructs it into two variables. The same deconstruction works in the foreach over directions, which gives dr and dc.
    • Array initializer with tuples. (int, int)[] directions = { (-1, 0), ... }; declares and fills the array in one statement.
    • Characters. 'O' in single quotes is a char, the type of every cell. A string such as "O" would not compile in a comparison with a char.
    • In-place change. board is a reference to the caller's arrays, so assigning board[r][c] = 'X' changes the board the caller passed. That is why the method returns void.
    • Bounds are checked before indexing. Reading board[-1][0] would throw an exception, so the neighbour's position is tested first.

    Complexity

    Let the board have m rows and n columns.

    Time: O(m * n). The first pass and the last pass visit each cell once. In the BFS each cell is enqueued at most once, and handling it looks at four neighbours.

    Space: O(m * n). The safe array has one entry per cell, and the queue can hold many cells at once.

    Edge cases and common mistakes

    • A single cell. O alone is on every edge, so it stays.
    • Thin boards. With one or two rows, or one or two columns, every cell is on the border, so nothing is captured: X X X X / X O O O / X X X X is unchanged.
    • A lone inner 'O'. A 3 by 3 board with an 'O' in the middle and 'X' everywhere else turns to all 'X'.
    • A ring. In a 5 by 5 board whose inner 3 by 3 block is a ring of 'O' around an 'X', the whole ring is captured, since it touches no edge.
    • Diagonal contact. A cell that touches an edge-connected region only at a corner is not part of it. In OXXXX / XOOOX / XXXOX / XOXOX / XXXOX the 'O' in the top-left corner touches the region below it only diagonally, and it stays because it is on the edge itself, while the lone 'O' at row 3, column 1 (counting from 0) is captured.

    Testing

    The method changes the board it receives. These boards, written row by row, give:

    • XXXX / XOOX / XXOX / XOXX becomes XXXX / XXXX / XXXX / XOXX.
    • O stays O.
    • OXXXX / XOOOX / XXXOX / XOXOX / XXXOX becomes OXXXX / XOOOX / XXXOX / XXXOX / XXXOX.
    • XXXXX / XOOOX / XOXOX / XOOOX / XXXXX becomes all X.
    • XXXX / XOOO / XXXX is unchanged: the 'O' cells are in the last column.
    • XXX / XOX / XXX becomes 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