Problem Statement
You are given a matrix mat
of size N x M
where each element is either 'O'
or 'X'
. You need to modify the matrix such that every 'O'
that is completely surrounded by 'X'
(on all four sides: top, bottom, left, and right) is replaced by 'X'
. An 'O'
is not surrounded by 'X'
if it is connected to the boundary of the matrix either directly or indirectly (through other 'O'
s).
The objective is to return the modified matrix where all completely surrounded 'O'
s are replaced with 'X'
, but the 'O'
s that are connected to the boundary remain unchanged.
Conditions:
- If an
'O'
is connected to the boundary (the first or last row/column), it is not surrounded and should not be replaced. - An
'O'
is considered surrounded if it is completely surrounded by'X'
on all four sides (up, down, left, right) and is not connected to the boundary.
Examples
Example 1:
Input: mat = [
['X', 'O', 'X', 'X'],
['X', 'O', 'O', 'X'],
['X', 'X', 'O', 'X'].
['X', 'O', 'X', 'X']
]
Output: [
['X', 'O', 'X', 'x'],
['X', 'O', 'O', 'X'],
['X', 'X', 'O', 'X'].
['X', 'O', 'X', 'X']
]
Explanation:
All 'O's in this matrix are connected to the boundary, either directly or through other 'O's. Therefore, none of the 'O's should be replaced.
Example 2:
Input: mat = [
['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 'O's at positions (1, 1), (1, 2), and (2, 2) are completely surrounded by 'X' and should be replaced with 'X'.
The 'O' at position (3, 1) is on the boundary, so it should not be replaced.