image.png
0. 鏈接
1. 題目
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.
2. 思路1: 遞歸
- 基本思路是:
- 先從四個邊界線上的元素作為起點, 將所有的O修改為A, 遞歸的將其鄰居節(jié)點、鄰居的鄰居節(jié)點O修改為A
- 再將所有的A轉(zhuǎn)換為X
- 分析:
- 過程中, 每個元素都被訪問2次
- 復(fù)雜度
- 時間復(fù)雜度
O(M*N) - 空間復(fù)雜度
O(1)
3. 代碼
# coding:utf8
from typing import List
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if len(board) == 0:
return
m = len(board)
n = len(board[0])
def to_alive(i, j):
if board[i][j] == 'O':
board[i][j] = 'A'
if i > 0:
to_alive(i - 1, j)
if i < m - 1:
to_alive(i + 1, j)
if j > 0:
to_alive(i, j - 1)
if j < n - 1:
to_alive(i, j + 1)
for i in range(m):
to_alive(i, 0)
if n > 1:
to_alive(i, n - 1)
for j in range(1, n - 1):
to_alive(0, j)
if m > 1:
to_alive(m - 1, j)
for i in range(m):
for j in range(n):
if board[i][j] == 'A':
board[i][j] = 'O'
elif board[i][j] == 'O':
board[i][j] = 'X'
def print_board(board):
print('[')
for each in board:
print('\t{}'.format(each))
print(']')
def my_test(solution, board):
print('input:')
print_board(board)
solution.solve(board)
print_board(board)
solution = Solution()
my_test(solution, [
['X', 'X', 'X', 'X'],
['X', 'O', 'O', 'X'],
['X', 'X', 'O', 'X'],
['X', 'O', 'X', 'X']
])
my_test(solution, [
['X', 'O', 'X', 'O', 'X', 'O', 'O', 'O', 'X', 'O'],
['X', 'O', 'O', 'X', 'X', 'X', 'O', 'O', 'O', 'X'],
['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'X', 'X'],
['O', 'O', 'O', 'O', 'O', 'O', 'X', 'O', 'O', 'X'],
['O', 'O', 'X', 'X', 'O', 'X', 'X', 'O', 'O', 'O'],
['X', 'O', 'O', 'X', 'X', 'X', 'O', 'X', 'X', 'O'],
['X', 'O', 'X', 'O', 'O', 'X', 'X', 'O', 'X', 'O'],
['X', 'X', 'O', 'X', 'X', 'O', 'X', 'O', 'O', 'X'],
['O', 'O', 'O', 'O', 'X', 'O', 'X', 'O', 'X', 'O'],
['X', 'X', 'O', 'X', 'X', 'X', 'X', 'O', 'O', 'O']
])
輸出結(jié)果
input:
[
['X', 'X', 'X', 'X']
['X', 'O', 'O', 'X']
['X', 'X', 'O', 'X']
['X', 'O', 'X', 'X']
]
[
['X', 'X', 'X', 'X']
['X', 'X', 'X', 'X']
['X', 'X', 'X', 'X']
['X', 'O', 'X', 'X']
]
input:
[
['X', 'O', 'X', 'O', 'X', 'O', 'O', 'O', 'X', 'O']
['X', 'O', 'O', 'X', 'X', 'X', 'O', 'O', 'O', 'X']
['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'X', 'X']
['O', 'O', 'O', 'O', 'O', 'O', 'X', 'O', 'O', 'X']
['O', 'O', 'X', 'X', 'O', 'X', 'X', 'O', 'O', 'O']
['X', 'O', 'O', 'X', 'X', 'X', 'O', 'X', 'X', 'O']
['X', 'O', 'X', 'O', 'O', 'X', 'X', 'O', 'X', 'O']
['X', 'X', 'O', 'X', 'X', 'O', 'X', 'O', 'O', 'X']
['O', 'O', 'O', 'O', 'X', 'O', 'X', 'O', 'X', 'O']
['X', 'X', 'O', 'X', 'X', 'X', 'X', 'O', 'O', 'O']
]
[
['X', 'O', 'X', 'O', 'X', 'O', 'O', 'O', 'X', 'O']
['X', 'O', 'O', 'X', 'X', 'X', 'O', 'O', 'O', 'X']
['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'X', 'X']
['O', 'O', 'O', 'O', 'O', 'O', 'X', 'O', 'O', 'X']
['O', 'O', 'X', 'X', 'O', 'X', 'X', 'O', 'O', 'O']
['X', 'O', 'O', 'X', 'X', 'X', 'X', 'X', 'X', 'O']
['X', 'O', 'X', 'X', 'X', 'X', 'X', 'O', 'X', 'O']
['X', 'X', 'O', 'X', 'X', 'X', 'X', 'O', 'O', 'X']
['O', 'O', 'O', 'O', 'X', 'X', 'X', 'O', 'X', 'O']
['X', 'X', 'O', 'X', 'X', 'X', 'X', 'O', 'O', 'O']
]
4. 結(jié)果
image.png
