0130-surrounded-regions¶
Try it on leetcode
Description¶
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: A region is surrounded if none of the
'O'cells in that region are on the edge of the board. Such regions are completely enclosed by'X'cells.
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.
Example 1:
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation:
In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.
Example 2:
Input: board = [["X"]]
Output: [["X"]]
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j]is'X'or'O'.
Solution(Python)¶
class Solution:
def solve(self, board: list[list[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
m = len(board)
n = len(board[0])
def dfs(i, j):
if (not(0 <= i <= m-1) or not (0<= j <= n-1) or not board[i][j] == "O"):
return
board[i][j] = "#"
dfs(i+1, j)
dfs(i-1, j)
dfs(i, j+1)
dfs(i,j-1)
for i in range(n):
if board[0][i] == "O":
dfs(0,i)
if board[m-1][i] == "O":
dfs(m-1, i)
for i in range(m):
if board[i][0] == "O":
dfs(i, 0)
if board[i][n-1] == "O":
dfs(i, n-1)
for i in range(m):
for j in range(n):
if board[i][j] == "O":
board[i][j] = "X"
elif board[i][j] == "#":
board[i][j] = "O"