目錄
- 零、題目描述
- 一、為什么這道題值得你花時間掌握？
- 二、題目拆解：提取核心關鍵點
- 三、解題思路：從邊界入手，反向標記
- 四、算法實現：深度優先遍歷（DFS）+ 兩次遍歷
- 五、C++代碼實現：一步步拆解
- 代碼拆解
- 時間復雜度
- 空間復雜度
- 七、坑點總結
- 八、舉一反三
- 九、總結
零、題目描述
題目鏈接：被圍繞的區域
題目描述：
示例 1：
輸入：board = [
[“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”]
]
解釋：底部的'O'位于邊緣，不被圍繞，因此保留；其他'O'被'X'圍繞，被替換為'X'。
示例 2：
輸入：board = [[“X”]]
輸出：[[“X”]]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j]為'X'或'O'
一、為什么這道題值得你花時間掌握？
如果你是第一次接觸這類連通區域問題，強烈建議先按順序看看我之前的兩篇文章：《力扣 200. 島嶼數量》和《力扣 695. 島嶼的最大面積》。
這兩篇就像“入門工具箱”：前者會手把手帶你搞懂“怎么用DFS逛遍整個網格”“為啥要標記走過的路”，還有洪水灌溉算法最核心的框架；后者則在這基礎上，教你怎么邊逛邊算面積、怎么盯緊最大的那塊區域。先吃透這兩篇，再看這篇博客時，面對遞歸方向、邊界檢查這些基礎操作就不會懵了——畢竟這篇文章不會再重復講這些啦，咱們重點聊更有意思的“思路升級”。
當然，如果你已經搞定前兩題，那這道題對你來說就是個超棒的“進階訓練場”，值得花時間啃下來：
首先，它能讓你徹底get到 “正難則反” 這種超好用的思維。前兩題都是 “正面硬剛” —— 直接數島嶼、算面積，但這道題要是直接琢磨“哪些O被圍住了”，保準越想越復雜。可反過來一想：“只要跟邊緣的O連上，就肯定沒被圍住”，一下子就簡單多了。這種“從對面找突破口”的思路，以后遇到復雜的連通問題，絕對能幫你少走很多彎路。
其次，它更像真實面試里會考察的樣子。前兩題主要看你會不會用DFS/BFS框架，而這道題還會悄悄觀察你的“流程設計能力”：怎么用個臨時標記區分特殊區域？怎么分兩次遍歷就把所有O安排明白？這些細節，恰恰是大廠想看出你是 “只會寫代碼”還是“真的懂算法” 的關鍵。
最后，學會它，以后遇到更復雜的題也能舉一反三。比如「力扣 417. 太平洋大西洋水流問題」，要找那些“既能流進太平洋又能流進大西洋”的地方，要是正面一個個檢查“這水能流到哪”，估計得算到天荒地老。但用這道題的思路反過來想：從兩大洋的邊上往回找，看哪些地方的水能夠流到岸邊，最后取個交集就行——你看，是不是跟這道題的反向思維如出一轍？
說白了，前兩題是教你“認工具”，這道題是教你“靈活用工具解決麻煩事”。花點時間搞懂它，你的算法思維就能從“會操作”升級到“會策略”，絕對不虧～
二、題目拆解：提取核心關鍵點
我們來先看原題：
給你一個 m x n 的矩陣 board ，由若干字符 ‘X’ 和 ‘O’ 組成，捕獲 所有 被圍繞的區域：
· 連接：一個單元格與水平或垂直方向上相鄰的單元格連接。
· 區域：連接所有 ‘O’ 的單元格來形成一個區域。
· 圍繞：如果您可以用 ‘X’ 單元格 連接這個區域，并且區域中沒有任何單元格位于 board 邊緣，則該區域被 ‘X’ 單元格圍繞。
通過 原地 將輸入矩陣中的所有 ‘O’ 替換為 ‘X’ 來 捕獲被圍繞的區域。你不需要返回任何值。
再結合所給的代碼框架和提示：
class Solution {
public:void solve(vector<vector<char>>& board) {}
};
要解決這道題，首先需要明確“被圍繞的區域”的定義：不與矩陣邊緣相連的所有’O’組成的區域，也就是上下左右被X包圍的那個區域的O。反之，任何與邊緣’O’相連的’O’都不會被圍繞（因為邊緣外不算’X’包圍）。
核心要素提煉：
- 矩陣元素為 ‘X’（障礙）和 ‘O’（目標區域），長寬的范圍是 1 ≤ m, n ≤ 200；
- 核心任務：區分“被圍繞的 ‘O’”和“不被圍繞的 ‘O’”，并將前者原地替換為 ‘X’；
- “被圍繞”的判定標準：區域中所有 ‘O’ 均不與矩陣邊緣（上、下、左、右邊界）相連，且被 ‘X’ 包圍。
關鍵點：
- 連通性規則：僅水平（左右）或垂直（上下）相鄰的 ‘O’ 屬于同一區域，斜對角不算，搜索時需遍歷四個方向；
- 邊界特殊性：任何與邊緣 ‘O’ 相連的區域都不會被圍繞（邊緣外無 ‘X’ 包圍）；
- DFS/BFS 搜索：需通過深度或廣度優先遍歷，標記與邊緣相連的 ‘O’ 區域；
- 標記與替換策略：
- 用臨時符號（如 ‘1’）標記“不被圍繞的 ‘O’”（與邊緣相連的區域）；
- 遍歷矩陣，將未標記的 ‘O’ 替換為 ‘X’，將臨時標記的 ‘1’ 恢復為 ‘O’；
- 邊界處理：搜索時需檢查坐標合法性（0 ≤ x < 行數 且 0 ≤ y < 列數），防止越界。
與前兩題（島嶼數量、島嶼最大面積）的共性（可復用的邏輯）：
- 遍歷框架：通過雙重循環遍歷每個單元格，發現目標元素（前兩題是 ‘1’，本題是邊緣 ‘O’）時觸發搜索；
- DFS 核心邏輯：遞歸遍歷上下左右四個方向，處理連通區域；
- 標記訪問：通過修改原矩陣元素（前兩題標記為 ‘0’，本題標記為 ‘1’）避免重復訪問；
- 方向數組：用
dx = [1,-1,0,0]、dy = [0,0,1,-1]定義四個方向，簡化坐標計算。
關鍵差異（本次重點掌握的新邏輯）：
-
從“正向搜索目標”到“反向標記安全區”：
- 前兩題直接搜索目標區域（島嶼）并計數/算面積；
- 本題先標記“不被圍繞的 ‘O’”（與邊緣相連的區域），再通過排除法處理“被圍繞的 ‘O’”。
-
兩次遍歷的流程設計：
- 第一次遍歷：從邊緣 ‘O’ 出發，用 DFS 標記所有相連的 ‘O’ 為 ‘1’（安全區）；
- 第二次遍歷：遍歷整個矩陣，完成替換（‘O’→’X’，‘1’→’O’）。
-
標記符號的選擇：
- 前兩題用 ‘0’ 標記已訪問的 ‘1’（覆蓋原元素不影響結果）；
- 本題需用矩陣中不存在的符號（如 ‘1’）作為臨時標記，避免與原元素沖突，最后需恢復為 ‘O’。
三、解題思路：從邊界入手，反向標記
題目拆解中也提到了這道題和前兩題“地毯式搜索所有區域”的思路不同，這道題的突破口就是邊緣的’O’ 里——只要挨著邊緣的’O’，那它肯定沒被圍住，這是板上釘釘的事兒。
要是按正常思路硬剛：寫個DFS去搜每個’O’，判斷它是不是該被改成’X’，估計會頭大到想掀桌子——我當時就卡了20多分鐘，越想越亂：
- 怎么判斷一個’O’到底挨沒挨邊界？總不能搜著搜著突然回頭查坐標吧？
- 就算搜到了邊界，怎么告訴上層遞歸“這一片都不能改”？難道要搞多個遞歸函數分別處理？
- 遞歸的終止條件更是一團亂麻：是先判斷邊界還是先標記？一步錯步步錯。
后來才反應過來：換個角度不就完了？既然邊緣的’O’和它的“朋友圈”都安全，那先把它們圈出來，接下來就收拾沒有被圈出來的“小可愛們”不就可以了？
核心邏輯：先標記，再清場
- 第一步：給“邊緣”貼標記
沿著矩陣的四條邊遍歷，但凡看到’O’，就用DFS遍歷下，把所有跟它連著的’O’都改為臨時符號標記（比如改成’1’）。這些貼了標簽的，都是“背景硬”的安全區，絕對不能動。
- 第二步：大掃除，分情況處理
再從頭到尾掃一遍矩陣：- 沒被標記的’O’：妥妥的“要被處理的”，全改成’X’；
- 被標記的’1’：把進士標記改回去，恢復成’O’——畢竟它們本來就是O。
和前兩題的思路對比：
| 題目 | 核心操作 | 標記目的 | 遍歷次數 |
|---|---|---|---|
| 島嶼數量 | 發現’O’則計數并淹沒 | 避免重復計數 | 1次 |
| 島嶼最大面積 | 發現’O’則計算面積并淹沒 | 避免重復計算 | 1次 |
| 被圍繞的區域 | 先用臨時符號標記邊緣連通區，再替換 | 區分安全區和被圍繞區 | 2次 |
你看，前兩題是“發現一個處理一個”，這題是“先圈范圍再批量處理”——思路一換，復雜題立馬變簡單~
四、算法實現：深度優先遍歷（DFS）+ 兩次遍歷
基于上述思路，我們用DFS實現標記，用兩次遍歷完成替換。下面是具體步驟：
- 邊緣遍歷：遍歷矩陣的四條邊（i=0、i=rows-1、j=0、j=cols-1），對每個’O’調用DFS；
- DFS標記：在DFS中，將當前’O’標記為’1’，并遞歸處理上下左右四個方向的相鄰’O’；
- 全局替換：遍歷整個矩陣，按規則替換字符（‘O’→’X’，‘1’→’O’）。
五、C++代碼實現：一步步拆解
下面結合代碼詳細說明：
class Solution {
public:int rows, cols; // 矩陣的行數和列數// 方向數組：上下左右四個方向（與島嶼問題相同）int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};void solve(vector<vector<char>>& board) {if (board.empty()) return; // 邊界處理：空矩陣直接返回rows = board.size();cols = board[0].size();// 第一步：遍歷四條邊緣，標記所有與邊緣相連的'O'為'1'// 遍歷上下邊緣（i=0 和 i=rows-1，j從0到cols-1）for (int j = 0; j < cols; j++) {if (board[0][j] == 'O') dfs(0, j, board);if (board[rows-1][j] == 'O') dfs(rows-1, j, board);}// 遍歷左右邊緣（j=0 和 j=cols-1，i從1到rows-2，避免重復遍歷角落）for (int i = 1; i < rows-1; i++) {if (board[i][0] == 'O') dfs(i, 0, board);if (board[i][cols-1] == 'O') dfs(i, cols-1, board);}// 第二步：遍歷整個矩陣，替換字符for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (board[i][j] == '1') {// 恢復安全區域為'O'board[i][j] = 'O';} else if (board[i][j] == 'O') {// 未標記的'O'是被圍繞的，替換為'X'board[i][j] = 'X';}}}}// DFS：將與邊緣相連的'O'標記為'1'void dfs(int x, int y, vector<vector<char>>& board) {// 標記當前位置為'1'（臨時標記，代表安全區域）board[x][y] = '1';// 遍歷四個方向for (int i = 0; i < 4; i++) {int nx = x + dx[i]; // 新行坐標int ny = y + dy[i]; // 新列坐標// 檢查邊界合法性，且相鄰位置是未標記的'O'if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && board[nx][ny] == 'O') {dfs(nx, ny, board); // 遞歸標記}}}
};
代碼拆解
1. 類成員變量解析
int rows, cols; // 存儲矩陣的行數和列數，避免在DFS中重復計算
int dx[4] = {1, -1, 0, 0}; // 方向偏移：下、上、右、左
int dy[4] = {0, 0, 1, -1}; // 配合dx實現四個方向的坐標計算
- 方向數組與前兩題完全一致，復用“上下左右”的遍歷邏輯；
rows和cols在solve中初始化，確保DFS中能快速判斷邊界。
2. solve函數核心流程
第一步：邊緣遍歷與標記
// 遍歷上下邊緣（i=0和i=rows-1）
for (int j = 0; j < cols; j++) {if (board[0][j] == 'O') dfs(0, j, board);if (board[rows-1][j] == 'O') dfs(rows-1, j, board);
}
// 遍歷左右邊緣（j=0和j=cols-1，跳過已遍歷的角落）
for (int i = 1; i < rows-1; i++) {if (board[i][0] == 'O') dfs(i, 0, board);if (board[i][cols-1] == 'O') dfs(i, cols-1, board);
}
- 為什么分兩次遍歷？
上下邊緣的角落（如(0,0)）會被i=0和j=0重復檢查，但DFS中會標記為’1’，第二次檢查時board[i][j]已不是’O’，因此不會重復遞歸，無需額外判斷。
第二步：全局替換
for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (board[i][j] == '1') board[i][j] = 'O'; // 恢復安全區域else if (board[i][j] == 'O') board[i][j] = 'X'; // 替換被圍繞區域}
}
- 這一步是解題的“收尾”：通過一次遍歷完成兩種替換，邏輯清晰且高效。
3. dfs函數核心邏輯
void dfs(int x, int y, vector<vector<char>>& board) {board[x][y] = '1'; // 立即標記為安全區域for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];// 邊界合法且是未標記的'O'才遞歸if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && board[nx][ny] == 'O') {dfs(nx, ny, board);}}
}
- 標記時機：進入DFS后立即將’O’改為’1’，避免同一單元格被多次遞歸（與前兩題“立即淹沒”邏輯一致）；
- 遞歸條件：僅對“在邊界內”且“未標記的’O’”遞歸，確保不越界且不重復處理。
示例運行過程（以示例1為例）
輸入矩陣：
[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]
]
第一步：邊緣遍歷
- 下邊緣（i=3）的(j=1)是’O’，觸發DFS：
- 標記(3,1)為’1’，檢查四周：上方(2,1)是’X’，其他方向無’O’，DFS結束。
此時矩陣變為：
[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","1","X","X"]
]
第二步：全局替換
- 遍歷所有單元格：
- (1,1)、(1,2)、(2,2)是’O’→替換為’X’；
- (3,1)是’1’→恢復為’O’。
最終結果：
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]
]
時間復雜度
| 操作步驟 | 具體分析 | 時間復雜度 |
|---|---|---|
| 邊緣遍歷 | 最多訪問4×max(m,n)個單元格（四條邊緣的總長度） | O(m+n) |
| DFS標記安全區 | 每個’O’最多被訪問1次（標記為’1’后不再處理） | O(m×n) |
| 全局替換操作 | 遍歷整個矩陣的m×n個單元格，執行替換邏輯 | O(m×n) |
| 總計 | 所有操作的總次數與矩陣大小（m×n）成正比 | O(m×n) |
空間復雜度
| 消耗場景 | 具體分析 | 空間復雜度 |
|---|---|---|
| DFS遞歸棧 | 最壞情況（全為’O’且邊緣有’O’）：遞歸深度可達m×n（如200×200全’O’矩陣） | O(m×n) |
| 原地修改存儲 | 無需額外數據結構，直接修改原矩陣（用’1’臨時標記） | O(1) |
| 總計 | 空間消耗由遞歸棧深度決定，最壞情況下與矩陣大小成正比 | O(m×n) |
七、坑點總結
-
邊緣遍歷不完整
?錯誤：只遍歷上下邊緣或左右邊緣，漏掉角落的’O’（如(0,0)）。
?解決：必須遍歷四條邊（i=0、i=rows-1、j=0、j=cols-1），確保所有邊緣’O’都被處理。 -
臨時標記與原字符沖突
?錯誤：用’O’或’X’作為臨時標記（如誤將安全區域標記為’O’，導致無法區分）。
?解決：使用矩陣中不存在的字符（如’1’、'#'等）作為臨時標記，避免沖突。 -
DFS邊界檢查順序
?錯誤：先判斷board[nx][ny] == 'O'，再檢查坐標是否越界（可能導致訪問無效坐標）。
?解決：先檢查坐標合法性（nx和ny是否在0rows-1和0cols-1范圍內），再判斷字符是否為’O’。 -
替換邏輯顛倒
?錯誤：將’1’替換為’X’，將’O’替換為’O’（完全錯誤）。
?解決：明確替換規則：'1'→'O'（恢復安全區），'O'→'X'（替換被圍繞區）。
八、舉一反三
掌握本題思路后，可解決以下類似問題，尤其是那些需要“反向標記”或“邊界連通性判斷”的場景：
-
LeetCode 417. 太平洋大西洋水流問題
問題：找到既能流向太平洋，又能流向大西洋的所有單元格。
思路：用本題“反向標記”的升級版——從太平洋邊緣（上、左）和大西洋邊緣（下、右）分別出發，標記所有能流向兩大洋的單元格，最后取交集。這種“從結果倒推起點”的邏輯，與本題的反向思維如出一轍。 -
LeetCode 1020. 飛地的數量
問題：計算無法從邊界離開的陸地（‘1’）的數量。
思路：與本題類似，先標記所有與邊界相連的’1’（可離開的），再統計未標記的’1’（飛地）數量，核心是“排除法”思維。 -
LeetCode 529. 掃雷游戲
問題：根據點擊位置，展開所有無地雷的連通區域。
思路：通過DFS/BFS從點擊位置出發，按規則標記并展開區域，考驗“條件遞歸”和“邊界處理”，與本題的搜索框架高度契合。
這些問題雖場景不同，但核心都離不開“連通區域標記”和“邊界特殊性利用”，掌握本題思路后，再解這些題會有種“一通百通”的感覺～
九、總結
「被圍繞的區域」是連通區域問題中對“邊界特殊性”考察的典型題目。它的核心思維是 “從邊緣反向標記安全區域，再通過一次遍歷完成狀態轉換”，這與前兩題的“正向搜索”形成互補。
解題的關鍵不是記住代碼，而是理解：
- 如何通過邊界特征（是否接觸邊緣）定義區域性質；
- 如何用臨時標記區分不同區域；
- 如何設計兩次遍歷實現原地修改。
掌握這些，你就能應對所有“基于邊界的連通區域劃分”問題，面試中再遇到類似題目也能游刃有余。
最后歡迎大家在評論區分享你的代碼或思路，咱們一起交流探討~ 🌟 要是有大佬有更精妙的思路或想法，懇請在評論區多多指點批評，我一定會虛心學習，并且第一時間回復交流噠！
這是封面原圖～ 喜歡的話先點個贊鼓勵一下唄～ 再順手關注一波，后續更新不迷路，保證讓你看得過癮！😉
)
