- categories: Code, Interview Question, leetcode, Medium
- source: https://leetcode.com/problems/surrounded-regions
- topics: 2D Array, DFS
You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:
- Connect: A cell is connected to adjacent cells horizontally or vertically.
- Region: To form a region connect every
'O'cell. - Surround: The region is surrounded with
'X'cells if you can connect the region with'X'cells and none of the region cells are on the edge of theboard.
To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.
Idea
Find edge regions using recursion, capture other cells that are not in edge regions. Use bool matrix to exclude visited region
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
N = len(board)
M = len(board[0])
edge_regions = [[False] * M for n in range(N)]
def form_region(i, j):
nonlocal edge_regions
if i < 0 or i >= N or j < 0 or j >= M or edge_regions[i][j]:
return
if board[i][j] == "O":
edge_regions[i][j] = True
form_region(i+1, j)
form_region(i-1, j)
form_region(i, j+1)
form_region(i, j-1)
for i in [0, N-1]:
for j in range(M):
if board[i][j] == "O" and not edge_regions[i][j]:
form_region(i, j)
for i in range(N):
for j in [0, M-1]:
if board[i][j] == "O" and not edge_regions[i][j]:
form_region(i, j)
for i in range(1, N-1):
for j in range(1, M-1):
if board[i][j] == "O" and not edge_regions[i][j]:
board[i][j] = "X"