優先搜索（DFS）實戰

一、DFS通用解題思路?

二、逐題拆解?

三、四題對比

四、總結：DFS解決矩陣問題的“萬能模板”?

在算法解題中，矩陣連通性問題是高頻考點，而深度優先搜索（DFS）是解決這類問題的核心工具之一。它通過“一條路走到底，不通再回頭”的思路，能高效遍歷矩陣中相鄰的元素，進而完成標記、計數或替換等操作。本文將結合 LeetCode 130.被圍繞的區域、695.島嶼的最大面積、200.島嶼數量和 733.圖像渲染四題，拆解DFS在矩陣問題中的通用解題框架，并對比各題的差異點，幫助大家舉一反三。
?

一、DFS通用解題思路
?

矩陣問題的核心是“相鄰元素”的處理（通常指上下左右四個方向，特殊情況會包含對角線），DFS的作用就是從一個起始點出發，遍歷所有與起始點連通的元素，并執行特定操作（如標記、修改值）。其通用步驟可歸納為：
?
1.?邊界判斷：遍歷矩陣時，先檢查當前元素是否越界（行號<0或>=矩陣行數，列號<0或>=矩陣列

數），若越界則直接返回，避免程序報錯。
?

2.?條件篩選：判斷當前元素是否符合“可遍歷”條件（如是否為目標值、是否已被標記），若不符合

則返回，減少無效遍歷。
?

3.?執行操作：對符合條件的當前元素執行操作（如標記為已訪問、修改數值），防止后續重復遍

歷。
?

4.?遞歸遍歷：分別向當前元素的上、下、左、右四個方向遞歸調用DFS，繼續遍歷連通元素。
?
這四題均圍繞該框架展開，差異僅在于“條件篩選”和“執行操作”的具體內容，接下來我們逐題分析。
?

二、逐題拆解
?

1. LeetCode 130.被圍繞的區域——“邊界連通元素的保護”
?
題目核心需求
?
給定一個 ?m x n??的矩陣，將所有被 ?'X'??圍繞的 ?'O'??替換為 ?'X'?，與矩陣邊界直接或間接連通的 ?'O'??需保留。
?
解題關鍵
?
被圍繞的 ?'O'??的本質是“不與邊界連通”，因此我們可以先標記出所有與邊界連通的 ?'O'?，再將未被標記的 ?'O'??替換為 ?'X'?，最后還原被標記的 ?'O'?。
?
DFS實現步驟
?
1.?邊界遍歷：先遍歷矩陣的四條邊界（第一行、最后一行、第一列、最后一列），若遇到 ?'O'?，則以該元素為起點執行DFS。
2.?DFS標記：在DFS中，將與邊界連通的 ?'O'??標記為臨時符號（如 ?'*'?），避免后續被誤替換。
3.?矩陣更新：遍歷整個矩陣，將剩余的 ?'O'?（未與邊界連通，即被圍繞的）替換為 ?'X'?，將 ?'*'??還原為 ?'O'?。
?
關鍵代碼片段

// DFS：標記與邊界連通的'O'為'*'
void dfs(int x, int y, vector<vector<char>>& board) {// 1.邊界判斷 + 2.條件篩選（非'O'則返回）if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] != 'O') {return;}// 3.執行操作：標記為'*'board[x][y] = '*';// 4.遞歸遍歷四個方向dfs(x + 1, y, board);dfs(x - 1, y, board);dfs(x, y + 1, board);dfs(x, y - 1, board);
}void solve(vector<vector<char>>& board) {if (board.empty()) return;int m = board.size(), n = board[0].size();// 遍歷邊界，標記連通的'O'for (int i = 0; i < n; i++) {if (board[0][i] == 'O') dfs(0, i, board); ? ? ? // 第一行if (board[m-1][i] == 'O') dfs(m-1, i, board); ? // 最后一行}for (int i = 0; i < m; i++) {if (board[i][0] == 'O') dfs(i, 0, board); ? ? ? // 第一列if (board[i][n-1] == 'O') dfs(i, n-1, board); ? // 最后一列}// 更新矩陣for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == 'O') board[i][j] = 'X'; ?// 未標記的'O'替換為'X'if (board[i][j] == '*') board[i][j] = 'O'; ?// 標記的'*'還原為'O'}}
}

2. LeetCode 200.島嶼數量——“連通區域的計數”
?
題目核心需求
?
給定一個 ?m x n??的二進制矩陣，?'1'??代表陸地，?'0'??代表水域，計算矩陣中島嶼的數量（島嶼是由相鄰的 ?'1'??組成的連通區域，相鄰指上下左右）。
?
解題關鍵
?
每遇到一個未被訪問的 ?'1'?，就通過DFS遍歷其所有連通的 ?'1'??并標記為已訪問，每完成一次這樣的DFS，島嶼數量加1。
?
DFS實現步驟
?
1.?矩陣遍歷：遍歷矩陣中的每個元素，若遇到 ?'1'??且未被標記，則島嶼數量加1，并執行DFS。
2.?DFS標記：在DFS中，將當前的 ?'1'??標記為 ?'0'?（或其他符號），表示已訪問，避免重復計數。
3.?遞歸遍歷：向四個方向遞歸，將連通的 ?'1'??全部標記為 ?'0'?。
?
關鍵代碼片段
?
?

void dfs(int x, int y, vector<vector<char>>& grid) {// 1.邊界判斷 + 2.條件篩選（非'1'則返回）if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] != '1') {return;}// 3.執行操作：標記為'0'（已訪問）grid[x][y] = '0';// 4.遞歸遍歷四個方向dfs(x + 1, y, grid);dfs(x - 1, y, grid);dfs(x, y + 1, grid);dfs(x, y - 1, grid);
}int numIslands(vector<vector<char>>& grid) {if (grid.empty()) return 0;int m = grid.size(), n = grid[0].size();int count = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') { ?// 遇到未訪問的陸地count++;dfs(i, j, grid); ? ? ?// 標記整個島嶼}}}return count;
}

3. LeetCode 695.島嶼的最大面積——“連通區域的最大尺寸”
?
題目核心需求
?
給定一個 ?m x n??的二進制矩陣，?1??代表陸地，?0??代表水域，計算矩陣中最大島嶼的面積（島嶼面積為連通的 ?1??的個數）。
?
解題關鍵
?
與“島嶼數量”類似，但DFS需額外統計每個島嶼的面積（即連通的 ?1??的個數），并實時更新最大值。
?
DFS實現步驟
?
1.?矩陣遍歷：遍歷每個元素，若遇到 ?1??且未被標記，執行DFS并計算該島嶼的面積。
2.?DFS計數：在DFS中，將當前 ?1??標記為 ?0?（已訪問），并返回“1 + 四個方向連通區域的面積之和”，即當前島嶼的總面積。
3.?更新最大值：每次計算出一個島嶼的面積后，與當前最大值比較，保留較大值。
?
關鍵代碼片段

int dfs(int x, int y, vector<vector<int>>& grid) {// 1.邊界判斷 + 2.條件篩選（非1則返回0，無面積）if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] != 1) {return 0;}// 3.執行操作：標記為0（已訪問）grid[x][y] = 0;// 4.遞歸遍歷四個方向，累加面積return 1 + dfs(x+1, y, grid) + dfs(x-1, y, grid) + dfs(x, y+1, grid) + dfs(x, y-1, grid);
}int maxAreaOfIsland(vector<vector<int>>& grid) {if (grid.empty()) return 0;int m = grid.size(), n = grid[0].size();int maxArea = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {int area = dfs(i, j, grid); ?// 計算當前島嶼面積maxArea = max(maxArea, area); // 更新最大值}}}return maxArea;
}

4. LeetCode 733.圖像渲染——“指定區域的顏色替換”
?
題目核心需求
?
給定一個 ?m x n??的圖像（由整數表示顏色），以及一個起始坐標 ?(sr, sc)??和新顏色 ?newColor?，將起始坐標所在的“連通區域”（顏色與起始坐標原顏色相同，相鄰指上下左右）全部替換為新顏色。
?
解題關鍵
?
若起始坐標的原顏色與新顏色相同，直接返回圖像（避免無限遞歸）；否則通過DFS遍歷所有連通的原顏色像素，替換為新顏色。
?
DFS實現步驟
?
1.?初始判斷：記錄起始坐標的原顏色 ?oldColor?，若 ?oldColor == newColor?，直接返回圖像。
2.?DFS替換：在DFS中，將當前像素的顏色替換為 ?newColor?，并向四個方向遞歸，僅替換顏色為 ?oldColor??的像素。
?
關鍵代碼片段

void dfs(int x, int y, int oldColor, int newColor, vector<vector<int>>& image) {// 1.邊界判斷 + 2.條件篩選（非oldColor則返回）if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != oldColor) {return;}// 3.執行操作：替換為新顏色image[x][y] = newColor;// 4.遞歸遍歷四個方向dfs(x+1, y, oldColor, newColor, image);dfs(x-1, y, oldColor, newColor, image);dfs(x, y+1, oldColor, newColor, image);dfs(x, y-1, oldColor, newColor, image);
}vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {int oldColor = image[sr][sc];if (oldColor == newColor) return image; // 避免無限遞歸dfs(sr, sc, oldColor, newColor, image);return image;
}

三、四題對比

題目	核心操作??	條件篩選（DFS終止條件）	特殊處理?
130.被圍繞的區域	標記邊界連通的'O'	非'O'或越界	需還原標記（*→O）、替換未標記（O→X）
200.島嶼數量	標記陸地并計數	非'1'或越界	每啟動一次DFS，島嶼數+1?
695.最大島嶼面積	標記陸地并計算面積	非1或越界	DFS返回面積，實時更新最大值?
733.圖像渲染	替換連通區域的顏色	非原顏色或越界，原顏色==新顏色直接返回	直接替換為新顏色，無需還原?

四、總結：DFS解決矩陣問題的“萬能模板”
?

通過以上四題的分析，我們可以提煉出一個“矩陣DFS萬能模板”，只需根據題目需求修改?條件篩選?和?執行操作?即可：

// 通用DFS函數：x,y為當前坐標，其他參數根據題目需求補充（如矩陣、目標值、新值等）
void dfs(int x, int y, 額外參數) {// 1. 邊界判斷if (x < 0 || x >= 矩陣行數 || y < 0 || y >= 矩陣列數) {return;}// 2. 條件篩選（是否為目標元素、是否已訪問等）if (矩陣[x][y] 不滿足條件) {return;}// 3. 執行操作（標記、修改值、計數等）對矩陣[x][y]執行具體操作;// 4. 遞歸遍歷四個方向dfs(x + 1, y, 額外參數);dfs(x - 1, y, 額外參數);dfs(x, y + 1, 額外參數);dfs(x, y - 1, 額外參數);
}// 主函數：遍歷矩陣，觸發DFS
void mainFunction(矩陣類型& 矩陣, 其他參數) {if (矩陣為空) return;int 矩陣行數 = 矩陣.size(), 矩陣列數 = 矩陣[0].size();for (int i = 0; i < 矩陣行數; i++) {for (int j = 0; j < 矩陣列數; j++) {if (觸發DFS的條件) { // 如遇到未訪問的目標元素dfs(i, j, 額外參數);}}}// 若需后續處理（如還原標記、返回結果），在此處執行
}

矩陣連通性問題的本質是“找到并處理符合條件的連通區域”，DFS通過遞歸高效實現了這一過程。掌握上述模板后，無論題目要求是標記、計數還是替換，都能快速適配，真正做到“一題通，題題通”。