算法题--在二维矩阵中将所有被字母X包围的非边界O修改为X

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, 递归的将其邻居节点、邻居的邻居节点O修改为A
再将所有的A转换为X

分析:

过程中, 每个元素都被访问2次

复杂度

时间复杂度 O(M*N)
空间复杂度 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']
])

输出结果

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. 结果

image.png