难度: Medium
原题连接
内容描述
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.
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
Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******
因为boundary上的'O'肯定不会被包围
主要思路就是对boundary上是'O'的元素进行DFS，然后只要碰到'O'就继续走下去，直到碰到'X'或者碰到boundary，然后将这些'O'全部mark一下，即用'#'来替代， 最后我们遍历整个board，如果是'#'就变回'O'，如果是'X'或者'O'就变成'X'。
beats 90.02%
class Solution:
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
row = len(board)
col = len(board[0]) if row else 0
if not row:
return
for i in range(row):
for j in range(col):
if i == 0 or j == 0 or i == row - 1 or j == col - 1: # 点在boundary上
if board[i][j] == 'O': # 如果boundary上的元素为O,则进行dfs
self.mark(board, i, j)
for i in range(row):
for j in range(col):
if board[i][j] == '#':
board[i][j] = 'O'
else:
board[i][j] = 'X'
def mark(self, board, i, j):
row = len(board)
col = len(board[0])
if not 0 <= i < row or not 0 <= j < col or board[i][j] != 'O': # 退出dfs的条件：1.走到boundary；2.遇到'X'
return
board[i][j] = '#' # 表示该元素已被访问
self.mark(board, i - 1, j)
self.mark(board, i + 1, j)
self.mark(board, i, j - 1)
self.mark(board, i, j + 1)