【LeetCode 130. 被围绕的区域】

1. 题目

2. 分析

这题其实非常不错。如果正向解，非常麻烦；因为很难界定哪些O是被包围的？但是如果反向解呢？因为边界的O不会被包围，那么就可以想到跟边界O相连的O都不会被包围。那么除此之外的O都会被包围，题目就解决了。

3. 代码

class Solution:def solve(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""m, n = len(board), len(board[0])vis = [[0] * n for i in range(m)]# 只从边界遍历for i in [0,m-1]:for j in range(n):if board[i][j] == 'O':                self.dfs(i, j, m, n, vis, board)for j in [0, n-1]:for i in range(m):if board[i][j] == 'O':                self.dfs(i, j, m, n, vis, board)print(vis)for i in range(m):for j in range(n):if vis[i][j] == 0:board[i][j] = 'X'def dfs(self, i, j, m, n, vis, board):if i>=0 and j>=0 and i<m and j< n:if vis[i][j] == 0 and board[i][j] == "O":vis[i][j] = 1for item in [(i-1,j), (i, j-1), (i+1, j), (i, j+1)]:new_i, new_j = itemself.dfs(new_i, new_j, m, n, vis, board)