一、什么是深度優先遍歷（DFS）
以“深度”為第一關鍵詞，每次都沿路徑到不能再前進時，才退回到最近的岔路口，然后繼續按同樣的邏輯搜索，
二、題目與解答
題目：
Leetcode 695. 島嶼的最大面積
解答思路：
首先要遍歷陣列，當發現（i,j）對應為陸地時，進行如下步驟：
（1）遞回解法
遞回解法最重要的是首先要確定遞回邊界，
該題有兩個遞回邊界：
一個是矩陣尺寸限制，
一個是碰到了水域
一般來說，深度優先搜索型別的題可以分為主函式和輔函式，
主函式用于遍歷所有的搜索位置，判斷是否可以開始搜索，如果可以即在輔函式進行搜索，
輔函式則負責深度優先搜索的遞回呼叫
本題中主函式為：int maxAreaOfIsland(vector<vector<int>>& grid);
輔函式為：int LandDFS(vector<vector<int>>& grid, int i, int j); 其中i, j 代表當前坐標，
class Solution {
public:
// 輔函式
int LandDFS(vector<vector<int>>& grid, int i, int j)
{
// 在矩陣尺寸范圍內
if((i < grid.size()) && (i >= 0) && (j < grid[0].size()) && (j >= 0)) {
if (grid[i][j] == 0) { // 碰到水
return 0;
}
else {
grid[i][j] = 0;
return 1 + LandDFS(grid, i-1, j) + LandDFS(grid, i+1, j) +
LandDFS(grid, i, j-1) + LandDFS(grid, i, j+1);
}
}
else {
return 0;
}
}
// 主函式
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
ans = max(ans, LandDFS(grid, i, j)); // 這里LandDFS(grid, i, j)回傳的是含(i,j)的島嶼的面積
}
}
return ans;
}
};
（2）堆疊解法
我們也可以使用堆疊（stack）實作深度優先搜索，但因為堆疊與遞回的呼叫原理相同，而遞回相對便于實作，因此刷題時推薦使用遞回式寫法，同時也方便進行回溯（見下節），
不過在實際工程上，直接使用堆疊可能才是最好的選擇，一是因為便于理解，二是更不易出現遞回堆疊滿的情況，
class Solution {
private:
vector<int> direction {-1, 0, 1, 0, -1}; // 每相鄰兩位即為上下左右四個方向之一
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int localArea, area = 0, x, y;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j]) { // 進入島嶼
localArea = 1;
grid[i][j] = 0; // 抹除
stack<pair<int, int>> IsLand; // 存放土地的堆疊
IsLand.push({i, j}); // 往堆中加入當前土地（該島第一塊土地）
while (!IsLand.empty()) {
auto [r, c] = IsLand.top(); // 從堆中取出元素，并訪問
IsLand.pop(); // 從堆中取出元素，并訪問
for (int k = 0; k < 4; k++) { // 上下左右
x = r + direction[k];
y = c + direction[k+1];
if ( x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
++localArea;
grid[x][y] = 0;
IsLand.push({x, y}); // 往堆中加入當前土地 ( (i,j)土地的領接土地節點 )
}
}
}
}
area = max(area, localArea);
}
}
return area;
}
};
參考視頻：
https://leetcode.cn/problems/max-area-of-island/solution/dao-yu-de-zui-da-mian-ji-by-leetcode-solution/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539704.html
標籤：其他
上一篇：PYTHON爬取圖片