C# || How To Capture All Surrounded Regions ‘X’ & ‘O’ In Board Matrix Using C#

Print Friendly, PDF & Email

The following is a module with functions which demonstrates how to capture all surrounded regions ‘X’ and ‘O’ in a board matrix using C#.

1. Surrounded Regions – Problem Statement

Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Example 1:

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: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Example 2:

Input: board = [["X"]]
Output: [["X"]]

2. Surrounded Regions – Solution

The following is a solution which demonstrates how to capture all surrounded regions ‘X’ and ‘O’ in a board matrix.

This solution uses Breadth First Search when looking for surrounded regions.

A ‘O’ is surrounded if there is no path from it to the outer border of the matrix (i.e: row: index 0, column: index 0, row: index matrix.length-1, column: index matrix[0].length-1) when moving in a North, South, East, or West direction.


A 'O' will not be flipped to 'X' if:
It is on the border, OR
It is connected to any other 'O' that cannot be flipped

In this solution we get all ‘O’ cells around the borders and keep track of all ‘O’ cells connected to the ones around the outer border.

We mark the border ‘O’ cells, and all the connected ‘O’ cells to the ones around the outer border as invalid.

In the end, we mark all valid ‘O’ cells as ‘X’.

The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


Was this article helpful?
👍 YesNo

Leave a Reply