Surrounded regions
August 11, 2022
graphProblem URL: Surrounded regions
We will capture the surrounded reason by running DFS from each position and if it is not surrounded by the X
, then we turn them into a temporary value T
. Then after the DFS is done, we iterate over the whole grid one more time and convert all the O
to X
and all the T
to O
.
class Solution:
def solve(self, board: List[List[str]]) -> None:
ROWS, COLS = len(board), len(board[0])
def capture(r, c):
if (
r < 0
or c < 0
or r == ROWS
or c == COLS
or board[r][c] != "O"
):
return
board[r][c] = "T"
capture(r + 1, c)
capture(r - 1, c)
capture(r, c + 1)
capture(r, c - 1)
# (DFS) Capture unsurrounded regions (O -> T)
for r in range(ROWS):
for c in range(COLS):
if (
board[r][c] == "O"
and (r in [0, ROWS - 1] or c in [0, COLS - 1])
):
capture(r, c)
# Capture surrounded regions (O -> X) and (T -> O)
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == "O":
board[r][c] = "X"
elif board[r][c] == "T":
board[r][c] = "O"
Time Complexity: O(n*m)
Space Complexity: O(n*m)