被围绕的区域
# coding=utf-8# 被围绕的区域
"""
给你一个mxn的矩阵board，由若干字符'X'和'O'组成，捕获所有被围绕的区域：
连接：一个单元格与水平或垂直方向上相邻的单元格连接。
区域：连接所有'O'的单元格来形成一个区域。
围绕：如果您可以用'X'单元格连接这个区域，并且区域中没有任何单元格位于board边缘，则该区域被'X'单元格围绕。
通过将输入矩阵board中的所有'O'替换为'X'来捕获被围绕的区域。
"""class Solution1:def solve(self, board) -> None:# lowB解法"""Do not return anything, modify board in-place instead."""if len(board) == 0 or len(board[0]) == 0:returntemp_board = [[0 for _ in range(len(board[0]))] for _ in range(len(board))]m = len(board)n = len(board[0])for i in range(m): # copy.deepcopy可以解决 但是为了不引入就这样把for j in range(n):temp_board[i][j] = board[i][j]for i in range(m):for j in range(n):if temp_board[i][j] == 'O':if i - 1 >= 0 and i + 1 < m and j - 1 >= 0 and j + 1 < n:if (temp_board[i - 1][j] == 'X' or temp_board[i - 1][j] == 'O') and \(temp_board[i + 1][j] == 'X' or temp_board[i + 1][j] == 'O') and \(temp_board[i][j - 1] == 'X' or temp_board[i][j - 1] == 'O') and \(temp_board[i][j + 1] == 'X' or temp_board[i][j + 1] == 'O'):board[i][j] = 'X'print(board)class Solution:def solve(self, board) -> None:# 深度优先和广度优先就比较简单if not board:returntemp_board = [[0 for _ in range(len(board[0]))] for _ in range(len(board))]result_tmp = []def dfs(x, y):if board[x][y] == 'X':returnif [x, y] in result_tmp:returnresult_tmp.append([x, y])temp_board[x][y] = 1if y + 1 < n and temp_board[x][y + 1] != 1:dfs(x, y + 1)if y - 1 > -1 and temp_board[x][y - 1] != 1:dfs(x, y - 1)if x + 1 < m and temp_board[x + 1][y] != 1:dfs(x + 1, y)if x - 1 > -1 and temp_board[x - 1][y] != 1:dfs(x - 1, y)m = len(board)n = len(board[0])for i in range(m):for j in range(n):if board[i][j] == 'O' and (i == 0 or i == m - 1 or j == 0 or j == n - 1) and [i, j] not in result_tmp:dfs(i, j)for i in range(m):for j in range(n):if [i, j] not in result_tmp:board[i][j] = 'X'print(board)board = [["O", "O"], ["O", "O"]]
result = [["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "O", "X", "X"]]a = Solution()
a.solve(board)"""考虑过不用DFS或者BFS做，但是好像都太复杂了，只能这种方式好理解可以优化，性能不算好，就是边界找0，然后的话向内部联通，能联通就保存，注意找过的不要找了，这是常识这样比较耗时和占用空间的还是思维决定一切啊，哈哈可以看看lowB解法
"""
