Surrounded Regions

Similar Problems:

- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #dfs, #graph

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/surrounded-regions ## Basic Ideas: Graph ## ## First pass: Do dfs/bfs from the boarders, to keep 0s ## Second pass: change values ## ## Complexity: Time O(n*m), Space O(1) class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ if not board: return n, m = len(board), len(board[0]) def dfs(i, j): if i<0 or i>=n or j<0 or j>=m: return if board[i][j] != "O": return # Change 0 to 1 as visited board[i][j] = "1" dfs(i+1, j) dfs(i-1, j) dfs(i, j+1) dfs(i, j-1) # graph traverse from boarders boarders = [] for k in range(max(n, m)): boarders += [(0,k), (n-1,k), (k, 0), (k, m-1)] for i, j in boarders: dfs(i, j) for i in range(n): for j in range(m): if board[i][j] == "O": board[i][j] = "X" if board[i][j] == "1": board[i][j] = "O" return