Surrounded Regions
- 2 min read
- Graph
- LC-Medium
3 years ago
Solution
- Implement reverse thinking
- Instead of thinking of the areas that we can capture, think of the areas we cannot.
- Everything on the border cannot be captured, because if an element is on the border, it cannot be covered by 4 X's. The most number of X's it can be covered by is 3.
- So we go through all the cells on the border, and if it's an O, we mark it with another character 'T' indicating temporary, and do a DFS starting from here.
- Everything that's marked T indicates an element that cannot be capture. We do a DFS to get everything that's next to the O on the border. Any O that touches a border O by association cannot be surrounded on all sides by X's.
- After marking the regions we cannot capture with a 'T', we do go through the matrix value by value, and change 'O's to 'X's because they can be captured, and change 'T's back to O's because they cannot be captured
| Time | Space | Explanation |
|---|---|---|
O(mn) | O(mn) |
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
nrows, ncols = len(board), len(board[0])
def dfs(r, c):
if board[r][c] == 'O':
board[r][c] = 'T'
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr, nc = r + dr, c + dc
if nr >= 0 and nr < nrows and nc >= 0 and nc < ncols and board[nr][nc] == 'O':
dfs(nr, nc)
for r in range(nrows):
dfs(r, 0)
dfs(r, ncols - 1)
for c in range(ncols):
dfs(0, c)
dfs(nrows - 1, c)
for r in range(nrows):
for c in range(ncols):
if board[r][c] == 'T':
board[r][c] = 'O'
elif board[r][c] == 'O':
board[r][c] = 'X'