C# || How To Capture All Surrounded Regions ‘X’ & ‘O’ In Board Matrix Using C#
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:
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.
Basically:
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’.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 1, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to flip surrounded regions // ============================================================================ public class Solution { public void Solve(char[][] board) { var queue = new Queue<KeyValuePair<int, int>>(); // Get coordinates of 'O' cells on the left and right border and add to queue for (int row = 0; row < board.Length; ++row) { // Check left border if (board[row][0] == 'O') { queue.Enqueue(new KeyValuePair<int, int>(row, 0)); } // Check right border if(board[row][board[row].Length - 1] == 'O') { queue.Enqueue(new KeyValuePair<int, int>(row, board[row].Length - 1)); } } // Get coordinates of 'O' cells on the top and bottom border and add to queue for (int col = 0; col < board[0].Length; ++col) { // Check top border if (board[0][col] == 'O') { queue.Enqueue(new KeyValuePair<int, int>(0, col)); } // Check bottom border if (board[board.Length - 1][col] == 'O') { queue.Enqueue(new KeyValuePair<int, int>(board.Length - 1, col)); } } // 2D bool array to keep track of 'O' cells connected to the ones on the outer border var visited = new bool[board.Length][]; for (int row = 0; row < board.Length; ++row) { visited[row] = new bool[board[row].Length]; } // Search directions var directions = new List<KeyValuePair<int, int>>() { // Right new KeyValuePair<int, int>(0, 1), // Left new KeyValuePair<int, int>(0, -1), // Top new KeyValuePair<int, int>(-1, 0), // Bottom new KeyValuePair<int, int>(1, 0), }; // Find all 'O' cells connected to the ones on the outer border while (queue.Count > 0) { var current = queue.Dequeue(); // Get current coordinates var currentRow = current.Key; var currentCol = current.Value; // Mark cell as visited, which means its connected to a border cell visited[currentRow][currentCol] = true; // Search right, left, top, bottom for connected 'O' cells foreach (var direction in directions) { var newRow = currentRow + direction.Key; var newCol = currentCol + direction.Value; // Add connected cells to the queue if (IsValidCell(board, newRow, newCol) && board[newRow][newCol] == 'O' && !visited[newRow][newCol]) { queue.Enqueue(new KeyValuePair<int, int>(newRow, newCol)); } } } // Mark the 'O' cells not connected to outer borders as X for (int row = 0; row < board.Length; ++row) { for (int col = 0; col < board[row].Length; ++col) { if (board[row][col] == 'O' && !visited[row][col]) { board[row][col] = 'X'; } } } } private bool IsValidCell(char[][] board, int row, int col) { return row >= 0 && row < board.Length && col >= 0 && col < board[row].Length; } }// http://programmingnotes.org/ |
QUICK NOTES:
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:
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
[["X"]]
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply