給定一個(gè)二維的矩陣，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 圍繞的區(qū)域，并將這些區(qū)域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

X X X X X O O X X X O X X O X X

運(yùn)行你的函數(shù)后，矩陣變?yōu)?#xff1a;

X X X X X X X X X X X X X O X X

解釋:

被圍繞的區(qū)間不會(huì)存在于邊界上，換句話說(shuō)，任何邊界上的 ‘O’ 都不會(huì)被填充為 ‘X’。 任何不在邊界上，或不與邊界上的 ‘O’ 相連的 ‘O’ 最終都會(huì)被填充為 ‘X’。如果兩個(gè)元素在水平或垂直方向相鄰，則稱(chēng)它們是“相連”的。

DFS

所有的不被包圍的 O 都直接或間接與邊界上的 O 相連。

• 對(duì)于每一個(gè)邊界上的 O，我們以它為起點(diǎn)，標(biāo)記所有與它直接或間接相連的字母 O；
• 最后我們遍歷這個(gè)矩陣，對(duì)于每一個(gè)字母：
  • 如果該字母被標(biāo)記過(guò)，則該字母為沒(méi)有被字母 X 包圍的字母 O，我們將其還原為字母 O；
  • 如果該字母沒(méi)有被標(biāo)記過(guò)，則該字母為被字母 X 包圍的字母 O，我們將其修改為字母 X。

Code

def solve(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""if not board:returndef dfs(x, y):if not 0 <= x < rows or not 0 <= y < cols or board[x][y] != 'O':returnboard[x][y] = 'V'dfs(x + 1, y)dfs(x - 1, y)dfs(x, y + 1)dfs(x, y - 1)rows, cols = len(board), len(board[0])for r in range(rows):dfs(r, 0)dfs(r, cols - 1)for c in range(1, cols - 1):dfs(0, c)dfs(rows - 1, c)for r in range(rows):for c in range(cols):if board[r][c] == 'V':board[r][c] = 'O'elif board[r][c] == 'O':board[r][c] = 'X'

復(fù)雜度分析

• 時(shí)間復(fù)雜度：$O(n\times m)$，其中 $n$ 和 $m$ 分別為矩陣的行數(shù)和列數(shù)。深度優(yōu)先搜索過(guò)程中，每一個(gè)點(diǎn)至多只會(huì)被標(biāo)記一次。

• 空間復(fù)雜度：$O(n\times m)$，其中 $n$ 和 $m$ 分別為矩陣的行數(shù)和列數(shù)。主要為深度優(yōu)先搜索的棧的開(kāi)銷(xiāo)。

總結(jié)

以上是生活随笔為你收集整理的130. Surrounded Regions 被围绕的区域的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。