LC 0130 [M] Surrounded Regions
Code with Senpai edited this page Jun 15, 2022
·
2 revisions
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
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)
# 1. (DFS) Capture unsurrounded regions (O -> T) along the border mark with temp T
# islands/connected components along th eborder
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)
# 2. Capture surrounded regions (O -> X) everything that's still an O that wasn't changed to T
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == 'O':
board[r][c] = 'X'
# 3. Uncapture unsurrounded regions (T -> O)
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == 'T':
board[r][c] = 'O'
footer