Understanding the Problem
We are given a 2D matrix filled with characters 'X'
and 'O'
. The goal is to identify and convert all 'O'
regions that are completely surrounded by 'X'
into 'X'
s. An 'O'
region is defined as a group of connected 'O'
s (connected horizontally or vertically).
However, if any 'O'
in a region is on the border (top row, bottom row, leftmost column, or rightmost column), or is connected to a border 'O'
, that region is considered safe and should not be converted.
Step-by-Step Solution with Example
Step 1: Identify and understand the input
Let’s take this input matrix:
X X X X
X O O X
X X O X
X O X X
We need to determine which 'O'
s are surrounded and which are connected to the border.
Step 2: Mark the border-connected 'O's
Start by checking the border cells. If an 'O'
is found on the border, perform a BFS/DFS to mark it and all connected 'O'
s as safe (we can use a temporary marker like '#'
).
In our example, matrix[3][1]
is an 'O'
on the border. It is safe. We mark it as '#'
. But this 'O'
is not connected to any other 'O'
, so only this cell gets marked.
Step 3: Traverse the matrix to convert unsafe 'O's
Now scan the entire matrix:
- If a cell is
'O'
, it means it is not connected to any border 'O'
. It is unsafe and must be converted to 'X'
.
- If a cell is
'#'
, it was marked safe earlier and should be converted back to 'O'
.
After this step, our matrix becomes:
X X X X
X X X X
X X X X
X O X X
Step 4: Finalize the matrix
Replace all '#'
back to 'O'
. Now we have the final matrix with all truly surrounded regions converted and border-connected regions preserved.
Edge Cases
- Empty matrix: No operation needed.
- All 'X's: No changes required.
- All 'O's on border: No 'O' should be changed.
- Matrix with only 1 row or 1 column: All 'O's are border cells and remain unchanged.
Finally
This problem teaches us how to use graph traversal techniques like DFS or BFS to identify connected components, especially under constraints like "not surrounded." Marking safe regions with a temporary symbol is a common trick in matrix-based problems. Always process border-related constraints first and then use a second pass to finalize the result.
Comments
Loading comments...